Приложение 3. Машины Тьюринга

Основная цель оригинальной работы Тьюринга [1] состояла в том, чтобы решить Entscheidungsproblem Гильберта, проблему метаматематическую [2]. С этой целью он построил воображаемую вычислительную машину, которая стала известна как "машина Тьюринга". С тех пор эта конструкция используется для многих целей, и вследствие этого появилось много различных ее вариантов и много различных систем обозначений, более или менее близких первоначальным обозначениям Тьюринга. Мы опишем здесь коротко машину Тьюринга в обозначениях, согласующихся с обозначениями гл. 6.

Можно считать, что машина Тьюринга состоит из трех частей:

1. бесконечная лента, поделенная на квадраты (ячейки) (значит, "бесконечный" автомат), и конечное множество символов, которые можно вписывать в ячейки. На ленте находится
2. головка, которая может прочесть содержимое любой ячейки ленты, лежащей под ней (в каждый момент времени под ней находится только одна ячейка), может заменить этот символ на любой другой (или на тот же самый) и может сдвинуть ленту на одну ячейку влево или вправо. Что именно делает эта головка, определяет
3. управляющее устройство, представляющее собой автомат, который может находиться в конечном числе состояний и имеет набор инструкций, говорящих, что должна делать головка при каждом сочетании символа на ленте и состояния автомата. (Если же для получившейся комбинации не сказано, что делать, то машина останавливается.) Следовательно, машина Тьюринга - это детерминированный автомат, действие которого в момент t зависит от сочетания его входного символа и внутреннего состояния в момент t-1.

Если состояния автомата обозначать буквой q, символы на ленте буквой s и приказания сдвинуть ленту влево и право знаками ← и →, то всякая конкретная машина Тьюринга задается конечным набором инструкций вроде такого:

что означает: если автомат находится в состоянии q₃ и под головкой находится символ s₁, то в этой ячейке s₁ заменяется на s₀ и автомат переходит в состояние q₄; или такого:

что означает: если автомат находится в состоянии q₅ и под головкой находится s₀, то лента сдвигается на одну ячейку вправо и автомат остается в прежнем состоянии.

Поскольку все эти инструкции состоят из четырех знаков, их часто называют "четверками".

"Мгновенное описание" состояния машины состоит из всех символов, имеющихся в этот момент на ленте, записанных в том же порядке, причем обозначение состояния автомата, управляющего головкой, помещается в этой последовательности там, где находится головка, слева от символа, находящегося сейчас под головкой. (Когда пишется последовательность таких описаний, каждое отделяется от следующего за ним знаком <.)

"Универсальная машина Тьюринга" - это машина Тьюринга, способная выполнить любое вычисление, которое может выполнить любая другая машина Тьюринга. (Тьюринг доказал, что такая машина существует.)