Машина Тьюринга

Функция f(x)=x-3, если x<3 - зацикливается, кодировка двоичная,

Задание:

Для заданной вычислимой функции в заданной системе счисления

a.     Представить словесное описание вычисляющего функцию алгоритма, если исполнитель алгоритма может выполнять следующие действия:

i.    находить начало и конец слова,

ii.    передвигаться на один символ влево или вправо,

iii.    стирать слово или символ в начале-конце слова,

iv.    заменять текущий символ на другой символ алфавита,

v.    печатать стандартное слово-результат «да», «нет», «верно» и т.п.

b.     Составить вычисляющий алгоритм в одном из следующих исчислений: Машины Тьюринга/Нормальные алгоритмы Маркова.

c.     Привести не менее трех различных примеров применения алгоритма из пункта b) к входным словам, дающих разные конечные результаты,

d.     Для каждого входного слова-примера из пункта c) подсчитать количество потребовавшихся шагов алгоритма.