|
Предположим, что ячейки бумажной ленты могут содержать либо 0, либо 1, а головка, в зависимости от своего внутреннего состояния, может считывать ячейку, записывать в ячейку и передвигать ленту на одну ячейку вправо или влево. Конкретная машина Тьюринга будет выполнять серию операций в зависимости от того, что она обнаружит на ленте, и в соответствии со способом реагирования, на который настроена ее головка. Например, если она обнаруживает на ленте 1, когда сама находится в состоянии «1», она может заменить на ленте 1 на 0, поменять свое внутреннее состояние на «2» и сдвинуть ленту на один шаг вправо. В новой ячейке может оказаться 0. Когда головка находится в состоянии «2» и считывает 0, она, возможно, запрограммирована на сдвиг ленты на один шаг влево, а если она считывает 1, то меняет 1 на 0 и сдвигает ленту на один шаг вправо. Если реакции головки искусно запрограммированы, машину можно использовать для выполнения даже самых сложных вычислений. Реальное конструирование такой головки и ее реакций может быть весьма сложной процедурой, а вычисления могут быть очень медленными, но здесь нас интересует лишь принцип вычислений, а не их эффективность. Каждая из машин Тьюринга представляет собой специальное устройство из ленты и считывающей головки, определенным образом запрограммированной. Давайте предположим, что мы можем пронумеровать все возможные машины Тьюринга, так что у нас есть склад с ящиками, помеченными знаками t1 , t2 , и так далее. Если одна из этих машин принимает определенное число и останавливается, мы обнаружим определенное число на выходе. Например, если машина t10 принимает число 3, это может означать 42 на выходе и конец вычислений. Чтобы зарегистрировать этот результат, запишем t10(3) = 42 . Однако может существовать комбинация машины и значения числа, для которой вычисления никогда не закончатся, например, если машина t22 принимает число 17. Чтобы зарегистрировать этот результат, запишем t22(17) = ? . Перед Тьюрингом стояла задача узнать, существует ли способ проверки всех возможных машин и принимаемых ими значений чисел и принятия на основе этой проверки решения, будут ли вычисления когда-либо закончены. Чтобы выполнить эту программу, предположим, что существует универсальная машина Тьюринга , которая является такой машиной Тьюринга, которую можно запрограммировать для имитации любой индивидуальной машины Тьюринга. У этой машины входная лента имеет две секции, одна для программы, а другая для данных. Программная часть может состоять из строки чисел, которые инструктируют головку, как реагировать на то, что она обнаруживает на ленте. Например, код 001 может означать: — 279 —
|