Тьюринг не был автостроителем. Машина Тьюринга не предполагает двигателя внутреннего сгорания, поскольку все там перемещается исключительно силой мысли. Это математическая модель. Она чем-то может и напоминающая автомашину, но не более чем машину напоминает магнитофон, в котором лента (разделенная на ячейки) неподвижна, а считывающе-записывающая головка вдоль нее ездит. Хуже того, ездит головка рывками, от ячейки к ячейке. А в ячейках записаны символы. (Чтобы не было пустых ячеек, в пустые ячейки записывают специальный пустой символ).

В машине Тьюринга есть устройство управления, имеющее память «состояний» и работающее по задаваемой программе (алгоритму). Программа состоит из команд. Каждая «команда» состоит в следующем: Машина читает символ из ячейки, против которой стоит головка (находясь в каком-то состоянии [вначале – в начальном]), записывает в эту ячейку символ (может и тот же самый), меняет свое состояние (может сохранить прежнее) и делает шаг влево или вправо (может остаться на месте).

Так Машина ходит вдоль ленты до тех пор, пока не перейдет в специальное состояние, называемое заключительным. Это говорит об окончании работы Машины (алгоритма). А на ленте остается результат (решения).

Пример. Построим Машину, которая в сплошной последовательности единичек стирает последнюю.

Поскольку количество единичек в сплошной последовательности произвольное и неизвестное, последнюю определим как ту, которая стоит ПЕРЕД пустым символом. Это главная идея данного решения. Остальное – дело техники. Напишем программу – четыре команды.

Машина читает пустой символ, находясь в начальном состоянии пишет пустой символ и делает шаг вправо. (Значит машина находится ДО начала последовательности единичек)

Машина читает единичку, находясь в начальном состоянии, пишет единичку и делает шаг вправо, оставаясь в этом состоянии. (Значит машина «идет» по последовательности единичек)

Машина читает пустой символ, находясь в начальном состоянии, пишет пустой символ, делает шаг влево и переходит во второе состояние. (Значит найдена последняя единичка)

Машина читает единичку, находясь во втором состоянии, пишет пустой символ (стирает единичку), стоит на месте и переходит в заключительное состояние. (Задача решена)

Несмотря на внешнюю примитивность такой конструкции, для любой алгоритмически разрешимой задачи можно построить Машину Тьюринга! А поскольку машина строится в собственной голове, вопросы «технической эффективности» такой машины никакой роли не играют. Единственный вопрос. Доберется ли машина до заключительного состояния? Пусть и через (воображаемый) миллион лет. Тогда задача разрешима!

Не будет преувеличением сказать, что нормальные алгорифмы Маркова создал А.А.Марков, член-корреспондент Академии Наук СССР из Москвы. Для восстановления единообразия, по праву автора, он назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое, как и слово ариФметика…

Смысл нормальных алгорифмов – принудительный обмен, порядок которого жестко задан.

Собственно алгоритм в нормальных алгорифмах задается НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК – очередностью правил «что на что менять». Лучше всего это показать на примере замены слов, тем более, что и сам Марков любую последовательность букв, какую ни в одном словаре не сыщешь, называл «словами». Так при наличии двух подстановок: меняющей «ха» на «ссон» и «мусс» на «сл» из «муха» можно сделать «слон».