Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Si, не «вычеркнутые» на итерациях от 1-й до (i — 1) — й. Если ни одна из этих машин не останавливается не более чем за t(n — i) шагов, то задаем f(i) = 0. В противном случае пусть Mj будет первой машиной, которая остановится не более чем за t(n — i) шагов. Затем определяем f(i) как 1, если Mj выдает 0, и как 0, если Mj выдает 1. (Иными словами, мы заставляем Mj ошибиться при вычислении f(i).) Мы также «вычеркиваем» Mj в том смысле, что Mj не нужно будет моделировать в дальнейших итерациях. Так определяется функция f.

Конечно, f(n) можно вычислить за O(n²t(n)) шагов, просто смоделировав всю описанную выше итеративную процедуру. Ключевое наблюдение таково: для любого целого i, если мы жестко пропишем результат итераций с 1-й по i-ю в наш алгоритм моделирования (то есть сообщим алгоритму, какие Mj вычеркиваются в этих итерациях), мы можем пропустить итерации 1… i и перейти сразу к итерации i + 1. Более того, считая, что мы начинаем с итерации i + 1, мы можем вычислить f(n) всего за O(n²t(n — i) шагов вместо O(n²t(n)) шагов. Так что чем больше информации мы вычислим предварительно, тем быстрее алгоритм будет работать при достаточно больших входных n.

Чтобы превратить эту идею в доказательство, главное, что нужно сделать, — это показать, что моделирование итеративной процедуры — практически единственный способ вычислить f, или, более точно, что любой алгоритм вычисления f требует по крайней мере t (n — i) шагов для некоторых i. Это, в свою очередь, подразумевает, что для вычисления f не существует более быстрых алгоритмов.

Дополнительная литература

В следующих нескольких главах мы продолжим разбор теории вычислительной сложности. Однако для тех читателей, которых невозможно насытить информацией и которые действительно хотят глубоко разобраться в этом предмете, назову несколько своих любимых книг: Computational Complexity by Christos Papadimitriou (Addison-Wesley, 1994); Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak (Cambridge University Press, 2009); и The Nature of Computation, by Cristopher Moore and Stephan Mertens (Oxford University Press, 2011).

Загадка 1 из предыдущей главы

Можем ли мы считать без потери общности что компьютерная программа имеет доступ к собственному тексту? В качестве простого примера зададимся вопросом: существует ли программа, которая на выходе распечатывает сама себя?

Ответ: да, такие программы существуют. Более того, проходят даже конкурсы на то, кто напишет самую короткую самораспечатывающуюся программу. На международном конкурсе IOCCC (International Obfuscated C Code Contest)[28] несколько лет назад победила необычайно короткая программа. Догадайтесь, сколько в ней было символов: 30? 10? 5?

В победившей программе был ровно нуль знаков. (Подумайте об этом!) Правда, пустой файл нельзя все же назвать по-настоящему кошерной программой на языке C, но, судя по всему, некоторые компиляторы готовы скомпилировать его в программу, которая не будет ничего делать.

Хорошо, хорошо, но что если мы хотим получить нетривиальную программу, которая печатает сама себя? В этом случае стандартный фокус состоит в том, чтобы проделать примерно следующее (вы можете самостоятельно перевести это на свой любимый язык программирования):

Напечатать следующее дважды, второй раз в кавычках.

"Напечатать следующее дважды, второй раз в кавычках."

В общем, если вы хотите, чтобы программа имела доступ к собственному исходному коду, фокус в том, чтобы разделить программу на три части: (1) часть, которая на самом деле делает что-то полезное (она не обязательна); (2) «копировщик»; и (3) строка, которая будет копироваться. Строка, которую копируют, должна состоять из полного кода программы, включая копировщик. (Иными словами, она должна состоять из частей (1) и (2).) Тогда, прогнав копировщик дважды, мы получим свеженькую копию частей (1), (2) и (3).

Эту идею придумал фон Нейман в самом начале 1950-х. Вскоре после этого два человека (мне кажется, их звали Крик и Уотсон) нашли физическую систему, которая на самом деле следует этим правилам. Мы с вами, вместе со всеми живыми существами Земли, по существу, представляем собой живые компьютерные программы такого содержания:

Сделать ребенка, который действует по нижеследующей инструкции, а также содержит копию этой инструкции в своих репродуктивных органах.

"Сделать ребенка, который действует по нижеследующей инструкции, а также содержит копию этой инструкции в своих репродуктивных органах."

Загадка 2 из предыдущей главы

Если бы вода не была H2O, была бы она по-прежнему водой?

Ага, это на самом деле не есть хорошо определенный вопрос: все его содержание сводится к тому, что мы подразумеваем под словом вода. Задает ли вода «условия»: если вещество x прозрачное и мокрое, годится для питья и не имеет вкуса, образует при замерзании лед и т. п., то x и есть вода? При такой постановке вопроса само понятие воды можно определить, сидя в кресле, путем перечисления необходимых и достаточных условий того, чтобы нечто можно было считать водой. Затем мы выходим наружу — и все, что удовлетворяет нашим условиям, является водой по определению. Именно так считали Фреге и Рассел; в этом случае подразумевается, что все, что обладает «интуитивно понятными» свойствами воды, водой и является, вне зависимости от того, H2O это или не H2O.

Другой подход к этому вопросу, ставший визитной карточкой Саула Крипке[29], заключается в том, что слово вода «жестко обозначает» вполне конкретное вещество (H2O). С этой позиции мы сегодня можем точно сказать, что, когда древние греки или вавилоняне говорили о воде, они на самом деле имели в виду H2O, хотя и не понимали этого. Интересно, что в этом случае «вода = H2O» — необходимая истина, открытая путем эмпирических наблюдений. Нечто с теми же интуитивными свойствами, как у воды, но с другой химической структурой уже не было бы водой.

Крипке утверждает, что если принять точку зрения, предполагающую «жесткое обозначение», то одно из ее следствий будет связано с проблемой взаимоотношений сознания и тела. Идея в следующем: мечта редукциониста — объяснить сознание в терминах нейронных импульсов, точно так же, как наука объяснила воду как вещество с химической формулой H2O. Но Крипке говорит, что аналогия между двумя ситуациями неполна. В случае воды мы можем по крайней мере говорить осмысленно о какой-то гипотетической субстанции, которая выглядит и ощущается как вода, на вкус как вода и т. п., но имеет формулу, отличную от H2O, и