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

Для функции f=2x+3, кодировка двоичная

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

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

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

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

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

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

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

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

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

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