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

Чего не умеет компьютер?

Все известные компьютеры (в том числе и квантовый компьютер!) способны произвести не больше вычислений, чем произвела бы машина Тьюринга, будь у неё достаточно времени и памяти. Однако Тьюрингу удалось доказать, что некоторые математические задачи неразрешимы – то есть не могут быть решены машиной Тьюринга и, следовательно, ни одним из известных в наши дни компьютеров! Тьюринг показал это на примере задачи, касающейся самой машины Тьюринга. Эта задача получила название «проблема остановки».

Проблема остановки

Когда машина Тьюринга остановится? Если у неё есть только одно состояние (состояние 0), тогда необходимы только два правила: что делать, если машина читает 0; и что делать, если машина читает 1. Эти правила разными путями могут приводить к разным результатам, в зависимости от того, как формулировать правило для 1.

• Правило для 0 велит пропустить 0 и идти вправо, пока на входе не окажется 1, и тогда

сделать остановку. Машина останавливается и выдаёт ответ.

• Машина Тьюринга может зациклиться: при выборе «при чтении 1 записать 1 и вернуться влево» машина вернётся к предыдущему числу (0), затем, когда часы тикают следующий раз, по правилу для 0 перейдёт вправо и опять попадёт на 1; эта операция будет повторяться до бесконечности.

• Сделать машину Тьюринга, которая никогда не остановится, можно и по-другому. Если изменить правило для 1 в вид «при чтении 1 записать 0 и вернуться влево», то машина вернётся к предыдущему числу (0), затем перейдёт вправо, обнаружит в этот раз 0 и пойдёт дальше до следующей единицы. Таким образом, машина превратит все единицы в нули и навсегда уйдёт вправо.

Машина h

Сам Алан Тьюринг задавался вопросом: существует ли алгоритм, который при введении программы для какой-либо машины Тьюринга и неких внешних входных данных будет выдавать ответ 0, если эта машина с такими данными никогда не остановится и не выдаст ответа? Представим на миг, что такой алгоритм существует; тогда должна существовать машина Тьюринга, которая выполнит эту операцию. Более того, должна существовать машина, которая сможет проверить, может ли машина Тьюринга работать без остановки на собственной программе. Назовём эту машину h и введём данные – такие, чтобы h остановилась тогда и только тогда, когда входные данные – это программа машины Тьюринга, которая не останавливается при вводе собственной программы. Что произойдёт, если ввести в h такую программу?

Если она остановится, это будет пример машины Тьюринга, которая останавливается при введении собственной программы, – но ведь h была спроектирована так, чтобы не останавливаться при введении программы такой машины!

Если она не остановится – значит, это машина, которая не останавливается при введении собственной программы, но ведь при введении программы h в машину h она должна остановиться, поскольку она была сконструирована специально для того, чтобы выявлять такие машины.

В любом случае получается противоречие! Бессмысленная ситуация такого рода сообщает математикам: то, что они полагали истинным, неверно. Создание воображаемой машины Тьюринга h – существование которой невозможно – было, таким образом, правильной мыслью. Оно доказало, что не может быть машины Тьюринга, способной вычислить, может ли какая– либо машина Тьюринга с какими-либо входными данными работать без остановки. А раз этот вопрос нельзя решить с помощью машины Тьюринга – значит, на него нельзя получить ответ с помощью любого компьютера, устройство которого мы можем вообразить в настоящее время. Проще говоря, компьютер не может решить эту задачу.

Бесконечные числа

Количество возможных программ и машин Тьюринга бесконечно, но из-за того, что каждую компьютерную программу можно превратить в одно большое двоичное число, математик может описать множество всех программ или машин как счётно бесконечное, поскольку мы можем расположить их по размеру.

Но есть гораздо большие бесконечные числа, например бесконечность десятичных знаков с бесконечным числом знаков после запятой. Они называются «действительные числа». Существуют действительные числа, значения которых не могут быть выведены компьютером. Скажем, число «пи» (известное тебе из формулы длины окружности и равное приблизительно 3,142) можно посредством компьютера записать до любого десятичного знака. Эта последовательность начинается как 3,1415926535, а компьютер вычислил её до триллионов десятичных знаков. Большинство действительных чисел, однако, невозможно вычислить таким образом: они невычислимы по своей сути – компьютер не может этого сделать!

Будущее?

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