Алан Тьюринг. Оракул предсказывает из хаоса

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

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

Alan Turing

В классическом определении машина Тьюринга описывается как абстрактная модель компьютера, используемая для выполнения алгоритмов, состоящая из бесконечно длинной ленты, разделенной на поля, в которых записываются данные. Лента может быть бесконечной с одной стороны или с обеих сторон. Каждое поле может находиться в одном из N состояний. Машина всегда расположена над одним из полей и находится в одном из М-состояний. В зависимости от комбинации состояния машины и поля машина записывает новое значение в поле, меняет состояние и затем может переместить одно поле вправо или влево. Такая операция называется заказом. Машина Тьюринга управляется списком, содержащим любое количество таких команд. Числа N и M могут быть любыми, лишь бы они были конечными. Список инструкций для машины Тьюринга можно рассматривать как ее программу.

Базовая модель имеет входную ленту, разделенную на ячейки (квадраты), и головку ленты, которая может наблюдать только одну ячейку в любой момент времени. Каждая ячейка может содержать один символ из конечного алфавита символов. Условно считается, что последовательность входных символов размещается на ленте, начиная слева, остальные ячейки (справа от входных символов) заполняются специальным символом ленты.

Таким образом, машина Тьюринга состоит из следующих элементов:

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

Гиперкомпьютеры

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

Обложка книги об Алане Тьюринге

Проблема сплава, как показала работа Явы Зигельмана, опубликованная в 1993 году, может быть решена компьютером на основе нейронной сети, которая состоит из процессоров, соединенных друг с другом способом, имитирующим структуру мозга, с вычислительным результатом от одного, идущего на «вход» к другому. Появилась концепция «гиперкомпьютеров», которые используют фундаментальные механизмы Вселенной для выполнения вычислений. Это были бы — как бы экзотично это ни звучало — машины, выполняющие бесконечное число операций за конечное время. Майк Стэннетт из британского Шеффилдского университета предложил, например, использование электрона в атоме водорода, который в теории может существовать в бесконечном числе состояний. Даже квантовые компьютеры меркнут перед смелостью этих концепций.

В последние годы ученые возвращаются к мечте об «оракуле», который сам Тьюринг никогда не строил и даже не пытался. Эммет Редд и Стивен Янгер, специалисты Университета штата Миссури, считают, что можно создать «супермашину Тьюринга». Они идут по тому же пути, по которому пошла вышеупомянутая Хава Зигельман, строя нейронные сети, в которых на входе-выходе вместо значений ноль-единица присутствует целый спектр состояний — от сигнала «полностью включен» до « полностью выключен». Как объясняет Редд в июльском выпуске NewScientist за 2015 год, «между 0 и 1 лежит бесконечность».

Миссис Сигельман присоединилась к двум исследователям из Миссури, и вместе они начали исследовать возможности хаоса. Согласно популярному описанию, теория хаоса предполагает, что взмах крыльев бабочки в одном полушарии вызывает ураган в другом. Ученые, которые строят супермашину Тьюринга, имеют в виду примерно то же самое — систему, в которой небольшие изменения имеют большие последствия.

К концу 2015 года благодаря работе Зигельмана, Редда и Янгера должны быть построены два прототипа компьютеров, основанных на хаосе. Один из них представляет собой нейронную сеть, состоящую из трех обычных электронных компонентов, соединенных одиннадцатью синаптическими связями. Второе — это фотонное устройство, которое использует свет, зеркала и линзы для воссоздания одиннадцати нейронов и 3600 синапсов.

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

Однако, даже если прототипы супермашин, основанных на хаосе, будут работать, остается проблема, как доказать, что они действительно являются этими супермашинами. У ученых пока нет идеи для подходящего проверочного теста. С точки зрения стандартного компьютера, который можно было бы использовать для проверки этого, супермашины можно рассматривать как так называемые ошибочные, то есть системные ошибки. С человеческой точки зрения все может оказаться совершенно непонятным и… хаотичным.