Десять великих идей науки. Как устроен наш мир.

Предположим, что ячейки бумажной ленты могут содержать либо 0, либо 1, а головка, в зависимости от своего внутреннего состояния, может считывать ячейку, записывать в ячейку и передвигать ленту на одну ячейку вправо или влево. Конкретная машина Тьюринга будет выполнять серию операций в зависимости от того, что она обнаружит на ленте, и в соответствии со способом реагирования, на который настроена ее головка. Например, если она обнаруживает на ленте 1, когда сама находится в состоянии «1», она может заменить на ленте 1 на 0, поменять свое внутреннее состояние на «2» и сдвинуть ленту на один шаг вправо. В новой ячейке может оказаться 0. Когда головка находится в состоянии «2» и считывает 0, она, возможно, запрограммирована на сдвиг ленты на один шаг влево, а если она считывает 1, то меняет 1 на 0 и сдвигает ленту на один шаг вправо. Если реакции головки искусно запрограммированы, машину можно использовать для выполнения даже самых сложных вычислений. Реальное конструирование такой головки и ее реакций может быть весьма сложной процедурой, а вычисления могут быть очень медленными, но здесь нас интересует лишь принцип вычислений, а не их эффективность.

Каждая из машин Тьюринга представляет собой специальное устройство из ленты и считывающей головки, определенным образом запрограммированной. Давайте предположим, что мы можем пронумеровать все возможные машины Тьюринга, так что у нас есть склад с ящиками, помеченными знаками t ₁, t ₂, и так далее. Если одна из этих машин принимает определенное число и останавливается, мы обнаружим определенное число на выходе. Например, если машина  t ₁₀принимает число 3, это может означать 42 на выходе и конец вычислений. Чтобы зарегистрировать этот результат, запишем t ₁₀(3) = 42. Однако может существовать комбинация машины и значения числа, для которой вычисления никогда не закончатся, например, если машина  t ₂₂принимает число 17. Чтобы зарегистрировать этот результат, запишем t ₂₂(17) = . Перед Тьюрингом стояла задача узнать, существует ли способ проверки всех возможных машин и принимаемых ими значений чисел и принятия на основе этой проверки решения, будут ли вычисления когда-либо закончены.

Чтобы выполнить эту программу, предположим, что существует универсальная машина Тьюринга, которая является такой машиной Тьюринга, которую можно запрограммировать для имитации любой индивидуальной машины Тьюринга. У этой машины входная лента имеет две секции, одна для программы, а другая для данных. Программная часть может состоять из строки чисел, которые инструктируют головку, как реагировать на то, что она обнаруживает на ленте. Например, код 001 может означать:

001:если вы обнаруживаете на ленте 1 и находитесь в состоянии 1, замените 1 на 0, смените ваше внутреннее состояние на состояние 2 и передвиньтесь на один шаг вправо.

Подобным же образом, код 010 может означать:

010:если вы обнаруживаете на ленте 0 и находитесь в состоянии 2, передвиньтесь на один шаг влево; а если вы считываете 1, то замените 1 на 0 и передвиньтесь на один шаг вправо.

Программная часть ленты может выглядеть как …001010…, если эти две инструкции надо выполнить последовательно. Мы будем называть универсальную машину Тьюринга tu. Заметим, что, в то время как индивидуальнаямашина Тьюринга считывает только данные, универсальнаямашина сначала считывает программу, чтобы подготовить себя, а затем уж считывает данные. Так, если мы хотим, чтобы она имитировала t ₁₀, мы считываем программу 10, то есть множество инструкций, настраивающих машину на работу в режиме  t ₁₀, а затем скармливаем ей данные. Если данные состоят из числа 3, мы будем ожидать от этого совместного процесса ответ 42 и запишем tu(10,3) = 42, где первое число в скобках является номером машины Тьюринга, которую мы хотели имитировать, а второе число представляет данные.