Стивен Хокинг - Джордж и код, который не взломать
Снаружи раздался страшный грохот. Друзья вскрикнули и замерли. Они не шевелясь смотрели на дверь, которая сотрясалась под ударами, пока наконец не поддалась. На долю секунду Джорджа посетила безумная надежда: вдруг это Эрик и его друзья-учёные? Но увы: в подвал ворвались двое роботов Мерака, одинаковых как две капли воды.
Джордж повернулся к Эрботу. Андроид перенёс всё – похищение, космическую станцию, портал – и вернулся на Землю невредимым, только волосы были взлохмачены чуть больше обычного; но сейчас он наконец-то полностью разрядился и теперь безвольно съёжился в углу.
Старый Космос, эта величественная старинная машина, похоже, ничем не может им помочь. К тому же между ними и Космосом стоит Мерак, и сначала придётся иметь дело с ним. Неужели после всего пережитого они окажутся в плену у армии злобных роботов, которой командует безумный коротышка в детском комбинезончике, жаждущий мирового владычества? Неужели это и правда конец?
Джордж опять взял Анни за руку, и они тесно прижались друг к другу – погибать, так вместе.
Не оставалось даже проблеска надежды – но вдруг, не веря собственным глазам, они осознали, что роботы схватили не их, они схватили… Дубхе Алиота Мерака, который отчаянно извивался, пытаясь вырваться из стальных клешней.
– Пустите! Я приказываю! – рычал он. – Вы неправильно поняли команду! Не меня, жалкие железяки! Вот этих двоих! – Он дёрнулся, чтобы показать пальцем, но обе его руки были заведены за спину.
И тут снова заработал принтер.
Джордж бросился к компьютеру и оторвал лист с последним сообщением:
– Он думал, что он один умеет взламывать коды, – прочёл Джордж вслух, – перехватывать сообщения и изменять их содержание? Ха-ха-ха.
Джордж расхохотался.
– Анни, – с трудом выговорил он сквозь смех, – Космос перехватил управление армией роботов. Правда, старый вояка?
Космос мигнул огоньками.
– Да, это так, – написал он в ответ. – Все они, где бы ни находились, теперь будут служить людям. А эти двое будут сторожить этого человека до приезда Эрика.
– Космос, Космос, какой же ты молодчина! – Анни подбежала к нему, раскинув руки и явно намереваясь обнять, но остановилась, осознав, что обхватить его, пожалуй, не удастся. – Ты всех спас!
Чего не умеет компьютер?Все известные компьютеры (в том числе и квантовый компьютер!) способны произвести не больше вычислений, чем произвела бы машина Тьюринга, будь у неё достаточно времени и памяти. Однако Тьюрингу удалось доказать, что некоторые математические задачи неразрешимы – то есть не могут быть решены машиной Тьюринга и, следовательно, ни одним из известных в наши дни компьютеров! Тьюринг показал это на примере задачи, касающейся самой машины Тьюринга. Эта задача получила название «проблема остановки».
Проблема остановки
Когда машина Тьюринга остановится? Если у неё есть только одно состояние (состояние 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, а компьютер вычислил её до триллионов десятичных знаков. Большинство действительных чисел, однако, невозможно вычислить таким образом: они невычислимы по своей сути – компьютер не может этого сделать!
Будущее?
Некоторые теоретики полагают, что в будущем появятся новые виды компьютеров, основанные на неизвестных пока физических принципах, способные производить вычисления, недоступные машине Тьюринга, и что одним из этих компьютеров может даже оказаться человеческий мозг («первый вычислитель»).
– В следующий раз, – ответил Космос, – имейте в виду, что молодость – это прогресс, зато старость – это мудрость.
– Хорошо! – сказал Джордж. – Мы будем об этом помнить, прекрасная мудрая машина. А ты, – он обернулся к Мераку, который по-прежнему извивался как червяк, – останешься здесь, пока не приедет Эрик. Я так думаю, он применит к тебе исправление квантовых ошибок!
– Куда же вы? – плаксиво протянул Мерак. – Вы не можете бросить меня в этом подвале, с этими роботами! Так нечестно! Тут нечего есть, нечего пить, нечего делать. Это противоречит Международной конвенции по активности роботов. Я натравлю на вас моих адвокатов! Вы за это заплатите!
– Как это на него похоже, – поморщилась Анни. – Как только стало ясно, что он проиграл, сразу «так нечестно». Пока он выигрывал, его ничего не смущало!
– Покатили домой, Анни! – Джордж подхватил скейтборды и направился к лестнице, ведущей из подвала. – Не знаю, как ты, а я есть хочу – помираю!
– Стой! – остановила его Анни. – Мы не сказали спасибо Старому Космосу!
Джордж обернулся и улыбнулся громоздкому компьютеру:
– Спасибо, Космос! Ты спас не только нас – ты спас весь мир!
– На здоровье! – ответил Космос, сияя огоньками. – Так приятно быть полезным. Только, пожалуйста, расскажите всё это Эрику, во всех подробностях, – на случай, если он подумывает сдать меня в утиль.
