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

Современным математикам, программистам и компьютерным инженерам имя Алана Тьюринга хорошо знакомо еще со студенческой скамьи: всем им приходилось изучать "машину Тьюринга" — "основу основ" теории алгоритмов. Без "машины Тьюринга" не обходится ни один серьезный учебник по математической логике и теории вычислимости.

Почти за каждым выдающимся научным открытием стоит удивительная история. За "машиной Тьюринга" стоит история жизни научного гения — гения, который лишь через много лет после своей трагической смерти получил достойное признание.

Глава 1. Машина А. Тьюринга

§ 1.1. Неформальное и формальное описания

В этой главе мы рассмотрим еще один тип распознающих устройств — машины Тьюринга. Это абстрактное устройство было предложено в качестве математической модели для описания процедур. Так как наше интуитивное понятие процедуры как конечной последовательности инструкций, которые могут выполняться механически, не является математически точным, мы не можем доказать формально, что оно эквивалентно точному понятию машины Тьюринга. Однако из определения этого устройства будет очевидно, что любое вычисление, которое может быть описано посредством машины Тьюринга, может быть выполнено механически. Также может быть показано, что любое вычисление, которое может быть выполнено на современной вычислительной машине, может быть описано посредством машины Тьюринга.