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

• Правило для 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, а компьютер вычислил её до триллионов десятичных знаков. Большинство действительных чисел, однако, невозможно вычислить таким образом: они невычислимы по своей сути – компьютер не может этого сделать!

Будущее?

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

– В следующий раз, – ответил Космос, – имейте в виду, что молодость – это прогресс, зато старость – это мудрость.

– Хорошо! – сказал Джордж. – Мы будем об этом помнить, прекрасная мудрая машина. А ты, – он обернулся к Мераку, который по-прежнему извивался как червяк, – останешься здесь, пока не приедет Эрик. Я так думаю, он применит к тебе исправление квантовых ошибок!

– Куда же вы? – плаксиво протянул Мерак. – Вы не можете бросить меня в этом подвале, с этими роботами! Так нечестно! Тут нечего есть, нечего пить, нечего делать. Это противоречит Международной конвенции по активности роботов. Я натравлю на вас моих адвокатов! Вы за это заплатите!

– Как это на него похоже, – поморщилась Анни. – Как только стало ясно, что он проиграл, сразу «так нечестно». Пока он выигрывал, его ничего не смущало!

– Покатили домой, Анни! – Джордж подхватил скейтборды и направился к лестнице, ведущей из подвала. – Не знаю, как ты, а я есть хочу – помираю!

– Стой! – остановила его Анни. – Мы не сказали спасибо Старому Космосу!

Джордж обернулся и улыбнулся громоздкому компьютеру:

– Спасибо, Космос! Ты спас не только нас – ты спас весь мир!

– На здоровье! – ответил Космос, сияя огоньками. – Так приятно быть полезным. Только, пожалуйста, расскажите всё это Эрику, во всех подробностях, – на случай, если он подумывает сдать меня в утиль.

– Этого мы не допустим! – горячо пообещала Анни. – Ты теперь наш друг на веки вечные!

Над тихим университетским городком занимался рассвет; юные солнечные лучи позолотили фасады старинных зданий. В окнах, расположенных над арками и резными дверями, появлялись первые сонные лица, а по узким улочкам катили на скейтбордах Джордж и Анни, обсуждая свои представления о лучшем в мире завтраке.

– Блинчики, – сказал Джордж, и его рот наполнился слюной. – Целая башня из блинчиков с кленовым сиропом.

– Бекон! – сказала Анни. – Горячий хрустящий бекон.

– Бекон? – Джордж вздрогнул, подумав о своём старом друге, кабанчике Фредди.

– Ну, можно обойтись и без бекона, – уступила Анни. – Тем более дома всё равно никакой еды наверняка нет.

Джордж вспомнил, в каком состоянии были обе кухни в последний раз.

– Да-а, придётся потрудиться, чтобы привести там всё в порядок, – сказал он.

– Что же теперь будет? В смысле, как папа и остальные объяснят всему миру, что произошло? – спросила Анни, когда они уже подкатывали к Малой улице Сент-Мэри.