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