Реферат: Формализация понятия алгоритма
В качестве исполнителя алгоритмов им был предложен автомат, состоящий из:
бесконечной ленты, разбитой на ячейки;
каретки, способной передвигаться над лентой, от ячейки к ячейке, считывать символы, записанные на ленте, записывать символы в ячейки.
В каждой ячейке ленты может быть записан только один из определенного множества символов, называемого алфавитом. За одно срабатывание каретка способна выполнить следующие действия:
считать символ из ячейки, над которой она находится;
записать символ в ячейку, над которой она находится;
переместиться либо влево, либо вправо на следующую ячейку, либо остаться на месте.
изменять свое внутреннее состояние.
Поясним последний пункт. Предполагается, что каретка может находиться в одном из состояний, из определенного множества состояний. Одним из ее действий, на ряду с перечисленными выше, является переход из одного состояния в другое.
В терминах, упомянутых выше семи параметров машину Тьюринга можно определить следующим образом.
Совокупность возможных исходных данных - алфавит D;
Совокупность возможных результатов - алфавит D;
Совокупность возможных промежуточных результатов - алфавит D;
Множество действий:
множество правил вида ap®bqw, где a,bÎ D; p,qÎ Q; wÎ {Л, П, Н}.
D - алфавит символов, которые могут появляться на ленте;
Q - множество символов, обозначающих состояния каретки.
Л, П, Н - символы, обозначающие передвижение каретки налево, направо или наместе соответственно.
Смысл правила ap®bqw состоит в следующем. Если каретка находится над ячейкой, в которой записан символ а, и каретка находится в состоянии p, то каретка должна:
записать в эту ячейку символ b (символ а при этом стирается),
из состояния p перейти в состояние q,
переместиться на следующую ячейку влево если w=Л, - вправо если w=П или остаться на месте если w=Н.
Правило начала: каретка всегда размещается над последним, считая слева направо, символом слова на ленте и находится в специальном начальном состоянии qo ;
Правило окончания: есть специальное состояние, мы его будем обозначать символом ! из алфавита Q. Как только каретка переходит в состояние ! , она останавливается.
Например, если правило имеет вид ap®b!w , то после его выполнения вычисление считается законченным.
Правило расположения результата: справа от каретки до первого символа пустоты.
Дело в том, что пустота - это тоже символ, который мы будем обозначать символом 
L.
Пример 1. Построить Машину Тьюринга, вычисляющую функцию
U(n)=n+1 , где nÎ {0,1,2,3,4,5,6,7.8.9}.