Как вычислить значение x mod 2 на машине Тьюринга?

Question

[Berthellar]

Необходимо написать алгоритм для вычисления на машине Тьюринга значение (x mod 2), где x - натуральное число в унарном коде

Comments

[Berthellar]

Спасибо за ответы, но уже решил. Решение следующее:
1) Просматриваются 3 близлежащих числа
2) Если все три числа это 1, тогда первые два обнуляются и процедура повторяется, начиная с оставшейся единицы, пока не получится либо 1, либо 11

Answer 1

[mayton2019]

В унарном виде - это как цепочка единичек. Например число 5 будет.

_11111_

Справа и слева должен стоять blank sysmbol. Типа признак конца ленты чтоб было что проверять.

Тогда (5 mod 2) = 1

И мы должны получить на ленточке просто единичку.

_1_

Это можно сделать поглощая пары соседних единичек. А для четного числа будет пустая лента. Тоесть остаток от деления равен нулю.

Ну вот такой алгоритм. Дальше надо делать конечный автомат который ищет пары единичек.