Джордж и код, который не взломать

Универсальная машина тьюринга

Воображаемое устройство

В 1936 году «компьютером», то есть «вычислителем», называли не машину, а человека, который что-то вычисляет. Машина Тьюринга, придуманная гениальным математиком Аланом Тьюрингом, – воображаемое устройство, способное воспроизводить всё, что делает в хо де расчётов человек-компьютер. То есть машина Тьюринга – не реальный прибор, а математическое устройство, позволяющее понять, что такое вычисление и чего можно достичь путем вычислений. В реальности такой машины быть не может: например, у неё должны быть и бесконечная «память», и неограниченное время работы, а ни то, ни другое невозможно.

Цепочка нулей

Действие, выполняемое машиной, описывается конечным списком зашифрованных инструкций. Представим себе очень длинную ленту, на которой написана очень длинная цепочка нулей (такая же длинная, как сама лента). Эта лента, которая тянется бесконечно в обоих направлениях (предположим, что она бесконечно длинная), – «память» вычислительной машины. Между нулями вкраплено конечное число единиц – они представляют введённые в машину «данные». На ленте установлено управляющее устройство (процессор). Процессор может читать ровно один символ, проходящий через него в данный момент, и может либо ничего с ним не делать, либо заменить на 0 или 1.

Процессор также включает в себя часовой механизм, который ритмично тикает, и с каждым тиканьем процессор читает символ, который видит в данный момент. Затем он может сделать одно из двух – в зависимости от того, что он прочёл, и от своего текущего состояния. Он может:

• изменить прочитанный символ на 0 или 1; сдвинуться по ленте на одну позицию влево или вправо; возможно, перейти в другое состояние; ждать следующего тиканья;

• сделать всё то же, после чего остановиться (отключиться).

Что именно сделает процессор, зависит от правил («программы»), которые мы зададим, и от того, что он прочтёт на ленте. Предположим, что машина начинает работу в состоянии 0, с длинной цепочкой нулей на ленте, и где-то справа несколько нулей заменены единицами – эти единицы образуют в двоичной системе число, которое мы даём машине в качестве входных данных.

Тогда правило для начала работы выглядит так: если в состоянии 0 мы читаем 0 – перейти в состояние 0, написать 0 и перейти вправо.

Это означает, что если вначале машина видит 0 (находясь в состоянии 0), она остаётся в состоянии 0, не изменяет запись 0 на ленте и переходит на шаг вправо. Если следующий знак – опять 0, повторяется то же самое: машина остаётся в состоянии 0, не делает отметок на ленте и передвигается ещё на шаг вправо.

Всё это повторяется с каждым тиканьем часов, пока наконец машина не достигнет первой единицы на ленте. Теперь требуется правило, объясняющее, что делать, когда процессор читает 1 в состоянии 0. Простейшим правилом будет: оставаться в состоянии 0, записать 1, перейти на шаг вправо и остановиться. Теперь слева от машины будет записана единица, и это будет результат вычисления.

Этот алгоритм можно описать как «печатать 1, если входные данные корректны

», где «корректны» означает «содержат по меньшей мере одну единицу». Если бы на момент начала работы справа от управляющего устройства не было ни одной единицы, она бы никогда не остановилась, а продолжала бы движение в вечном и бесплодном поиске единицы. Такое может произойти и с настоящим компьютером: программа может «зациклиться», и в конце концов компьютер сломается.

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

Тьюринг также математически показал, что даже машина Тьюринга не может решить все задачи! Иными словами, некоторые задачи в математике не решаются с помощью вычислительной техники – то есть математиков пока нельзя заменить машинами.

Любое возможное вычисление

Если есть достаточно времени и есть возможность записать на ленте ввода нужное число единиц, то выполнимо любое механическое действие с целыми числами, какое только можно придумать. Для этого требуется дать машине Тьюринга входное число справа от машины, запустить часы, дождаться остановки – и прочесть ответ слева от машины. К таким действиям относится любой арифметический расчёт, какой может произвести человек с помощью ручки и бумаги. Алан Тьюринг предложил такое определение вычислимого: вычислимо то, что может вычислить машина Тьюринга. Удивительно, но спустя примерно 80 лет это определение по-прежнему считается верным: все известные компьютеры могут выполнять вычисления только в пределах возможностей машины Тьюринга.