От абака к цифровой революции

Он свел проблему разрешения к проблеме остановки и доказал, что она неразрешима с помощью его машины: нельзя определить алгоритмически, завершит ли данная машина Тьюринга свою работу в какой-то момент или нет. Чёрч и Тьюринг не соперничали; напротив, оба осознавали, что их модели, несмотря на формальные различия, были одинаково мощными, и объединили усилия.

* * *

КАК РАБОТАЕТ МАШИНА ТЬЮРИНГА?

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

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

МТ = (Γ, Σ, Ь, Q, q₀, f, F).

Его элементы определяются следующим образом.

• Γ — алфавит, символы которого записываются на ленте.

• Σ  Γ — алфавит, символы которого подаются на вход машины. Множество возможных входных символов является подмножеством символов, которые могут быть записаны на ленте. На ленте также будут находиться символы, записанные самой машиной.

• b  Γ, Ь  Σ: Ь определяет пустое пространство. Это символ, не принадлежащий множеству входных символов. Изначально лента содержит конечное число символов Σ; оставшаяся часть ленты (которая является бесконечной) заполнена символами Ь.

• Q — множество состояний.

• q₀   Q — начальное состояние.

• f — функция перехода. Для данного состояния и элемента, записанного на ленте, эта функция определяет новое состояние, записывает символ на ленте и перемещает считывающее устройство влево (I), вправо (D) или же оставляет неподвижным (Р). Таким образом, функция f является функцией вида f: Q x Γ —> Q x Γ х {I, D, Р}.

F  Q — множество конечных состояний.

* * *

В апреле 1936 года американский математик Алонзо Чёрч из Принстонского университета опубликовал работу о проблеме разрешения. Чёрч пришел к тому же выводу, что и Тьюринг, доказав, что не все в математике является вычислимым.