Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2020-08-20 | 155 |
5.00
из
|
Заказать работу |
|
|
Можно, впрочем, задать и иной вопрос. Предположим, что новая теория квантовой гравитации действительно окажется невычислимой теорией — в том, в частности, смысле, что она позволит нам сконструировать физическое устройство, способное решить проблему остановки. Будет ли этого достаточно для разрешения всех проблем, порожденных нашими размышлениями о доказательстве Гёделя—Тьюринга в первой части книги? Как ни удивительно, ответ — нет!
Попробуем разобраться, почему способность решить проблему остановки ничем нам не поможет. В 1939 году Тьюринг предложил одну важную концепцию, имеющую к этому вопросу самое непосредственное отношение, — концепцию оракула. Идея такова: оракул есть нечто (предположительно, воображаемый объект, существующий лишь в голове самого Тьюринга и вовсе не обязательно реализуемый физически), что действительно может решить проблему остановки. Так, если дать оракулу пару натуральных чисел q и n, то он через некоторое конечное время выдаст нам ответ ДА или НЕТ, в зависимости от того, завершится в конце концов вычисление Cq (n) или нет (см. §2.5). В §2.5 мы доказываем вывод Тьюринга о том, что такой оракул, действующий исключительно вычислительными методами, создать невозможно, однако там ничего не говорится о том, что оракул невозможно построить физически. Чтобы прийти к такому выводу, мы должны твердо знать, что физические законы являются по своей природе вычислительными — а мы этого не знаем, о чем, собственно, и идет, главным образом, речь во второй части. Следует также отметить, что физическая возможность создания оракула не является, насколько я могу судить, следствием из той точки зрения, которую я здесь отстаиваю. Как уже упоминалось, никто не требует, чтобы все проблемы остановки были доступны человеческому пониманию и проницательности, поэтому нет никаких оснований и полагать, что некое физически реализуемое устройство непременно справится со всеми этими проблемами своей физической реализуемости.
|
В дальнейшем обсуждении Тьюринг рассмотрел модификацию понятия вычислимости, когда оракула можно вызвать на любом желаемом этапе вычисления. Таким образом, машина с оракулом (выполняющим оракул-алгоритм) представляет собой самую обыкновенную машину Тьюринга, только к ее стандартным вычислительным операциям добавлена еще одна: «Вызвать оракул и спросить у него, завершается ли вычисление Cq (n); по получении ответа продолжать вычисление, учитывая полученный ответ». Оракул можно вызывать снова и снова, если появляется такая необходимость. Отметим, что машина с оракулом является точно таким же детерминированным объектом, как и обычная машина Тьюринга (это для иллюстрации того факта, что вычислимость и детерминизм суть совершенно разные вещи). В принципе, вселенная, которая функционирует детерминированно как машина с оракулом, точно так же возможна, как и вселенная, которая функционирует детерминированно как машина Тьюринга. («Игрушечные вселенные», описанные в §1.9 и в НРК, на с. 170, представляют собой, по сути, вселенные-машины-с-оракулом.)
Может ли оказаться так, что и наша собственная Вселенная функционирует как машина с оракулом? Любопытно, что с помощью приведенных в первой части книги аргументов оракул-машинная модель математического понимания «развенчивается» столь же успешно, как и аналогичная модель на основе машины Тьюринга, причем изменений почти не требуется. Нужно всего лишь взять доказательство из §2.5 и условиться, что запись «Cq (n)» обозначает теперь «выполнение q -й машиной с оракулом действия над натуральным числом n». Впрочем, лучше ввести другое обозначение, скажем, C ' q (n). Как и в случае обычных машин Тьюринга, мы можем составить (вычислимым образом) пронумерованный список машин с оракулом. Что касается их спецификаций, единственной дополнительной особенностью является то, что мы должны, помимо прочего, учитывать, на каких этапах вычисления вызывается оракул; никакой новой проблемы такой учет не составит. Далее мы заменяем алгоритм A (q, n) из §2.5 оракул-алгоритмом A '(q, n), который, в соответствии с исходным допущением, олицетворяет собой всю совокупность доступных человеческому пониманию и человеческой проницательности средств, необходимых для однозначного установления факта незавершаемости операции C ' q (n) оракула. В точности повторяя доказательство, приходим к следующему выводу:
|
G ' Для установления математической истины математики не применяют заведомо обоснованные оракул-алгоритмы.
Отсюда следует неутешительное заключение: физический процесс, функционирующий как машина с оракулом, наших проблем также не решит.
Вообще говоря, весь процесс можно повторить, применив его к «машинам с оракулом второго порядка», которым позволяется вызывать при необходимости оракул второго порядка — который способен установить, завершится работа обычной машины с оракулом или нет. Как и в предыдущем случае, приходим к выводу:
G '' Для установления математической истины математики не применяют заведомо обоснованные оракул-алгоритмы второго порядка.
Очевидно, что этот процесс можно повторять снова и снова — подобно многократной гёделизации, описанной нами в связи с возражением Q19. Для каждого рекурсивного (вычислимого) ординала α вводится концепция машины с оракулом α -го порядка, и мы снова получаем все тот же вывод:
Gα Для установления математической истины математики не применяют заведомо обоснованные оракул-алгоритмы α -го порядка, где α — любой вычислимый ординал.
Окончательное следствие из всего этого несколько даже пугает. Получается, что нам предстоит отыскать невычислимую физическую теорию, способную заглянуть дальше, чем описание машин с оракулом любого вычислимого уровня (или, возможно, еще дальше).
Нисколько не сомневаюсь, что найдутся читатели, которые скажут, что вот уж тут-то мои рассуждения окончательно растеряли последние крохи правдоподобия, которые в них еще оставались! И, разумеется, такие чувства вполне понятны. Непонятно лишь нежелание хотя бы ознакомиться со всеми доказательствами, которые я уже в подробностях приводил ранее. Нужно просто вновь пройти по всем доказательствам в главах 2 и 3, заменяя в них машины Тьюринга на машины с оракулом α -го порядка. Не думаю, что такая замена как-то существенно повлияет на суть этих доказательств, но меня, если честно, приводит в содрогание перспектива только ради нее повторять их здесь заново. Следует, впрочем, указать на еще одно обстоятельство: нет никакой необходимости в том, чтобы человеческое понимание приобрело ту же мощь, что и какая угодно машина с оракулом. Как было отмечено выше, вывод G вовсе не обязательно предполагает, что человеческого понимания, в принципе, достаточно для того, чтобы решить любой конкретный случай проблемы остановки. Таким образом, все это не означает, что искомые физические законы в принципе должны непременно оказаться, более общими, нежели те, которыми описываются машины с оракулом любого вычислимого уровня (или хотя бы первого). Нам нужно лишь отыскать нечто, не являющееся эквивалентом любой конкретной машины с оракулом (включая сюда и машины с оракулом нулевого уровня, т.е. собственно машины Тьюринга). Возможно, эти физические законы опишут нечто просто-напросто иное.
|
|
|
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!