Извините за запоминающееся название. Я хочу понять, что нужно сделать, чтобы опровергнуть тезис Черча-Тьюринга? Где-то я читал, что это математически невозможно сделать! Почему?
Тьюринг, Россер и т. Д. Использовали разные термины, чтобы различать: «что можно вычислить» и «что можно вычислить с помощью машины Тьюринга».
Определение, данное Тьюрингом в 1939 году, таково: «Мы будем использовать выражение« вычислимая функция »для обозначения функции, вычисляемой машиной, и мы дадим« эффективно вычислимой »ссылку на интуитивную идею без особой идентификации с каким-либо из этих определений».
Итак, тезис Черча-Тьюринга можно сформулировать так: каждая эффективно вычисляемая функция является вычислимой.
Итак, еще раз, как будет выглядеть доказательство, если опровергнуть эту гипотезу?
источник
Ответы:
Тезис Черча-Тьюринга был доказан для всех практических целей.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402
Дершовиц и Гуревич, Бюллетень символической логики, 2008.
(Эта ссылка обсуждает историю работы Чёрча и Тьюринга и выступает за разделение «тезиса Чёрча» и «тезиса Тьюринга» как отдельных логических утверждений, а затем доказывает их обоих в рамках интуитивной аксиоматизации вычислимости.)
источник
Есть тонкий момент, который я редко вижу в подобных дискуссиях, и который, я думаю, заслуживает большего внимания.
Предположим, что, как предполагает Андрей, кто-то создает устройство, которое надежно вычисляет функцию которая не может быть вычислена ни одной машиной Тьюринга. Откуда нам знать, что машина на самом деле вычисляет ?фf f
Очевидно, что конечного числа входных / выходных значений будет недостаточно, чтобы продемонстрировать, что машина вычисляет в отличие от некоторой другой вычислимой по Тьюрингу функции, которая согласуется с на этом конечном множестве. Следовательно, наша вера в то, что машина вычисляет , должна основываться на наших физических теориях о том, как машина работает. Если вы посмотрите на некоторые конкретные предложения для гиперкомпьютеров, вы обнаружите, что, конечно же, они берут какую-то фантастическую передовую физическую теорию и экстраполируют эту теорию на бесконечностьф фf f f , Хорошо, хорошо, но теперь предположим, что мы создаем гиперкомпьютер и спрашиваем его, остановится ли когда-нибудь машина Тьюринга, которая ищет противоречие в ZFC. Предположим далее, что гиперкомпьютер отвечает «Нет». На чем мы заключаем? Делаем ли мы вывод, что гиперкомпьютер «вычислил» согласованность ZFC? Как мы можем исключить возможность того, что ZFC на самом деле несовместим, и мы только что провели эксперимент, который подделал нашу физическую теорию?
Важной особенностью определения Тьюринга является то, что его философские предположения очень слабы. Он предполагает, как и положено, определенные простые особенности нашего повседневного опыта, такие как базовая стабильность физического мира и способность выполнять конечные операции надежным, воспроизводимым и проверяемым образом. Эти вещи каждый принимает (за пределами классной комнаты философии, то есть!). Однако принятие гиперкомпьютера, похоже, требует от нас бесконечной экстраполяции.физической теории, и весь наш опыт работы с физикой научил нас не быть догматичными в отношении обоснованности теории в режиме, который намного превосходит то, что мы можем экспериментально проверить. По этой причине мне кажется крайне маловероятным, что когда-либо возникнет какой-либо всепоглощающий консенсус в отношении того, что любой конкретный гиперкомпьютер просто вычисляет, а не гиперкомпьютирует , т. Е. Делает что-то, что можно назвать «вычислением», только если вы принимаете некоторые противоречивые философские или физические предположения о бесконечных экстраполяциях.
Иными словами, для опровержения тезиса Черча-Тьюринга необходимо не только создать устройство, которое описывает Андрей, но и доказать всем, что устройство работает так, как рекламируется. Хотя это и немыслимо, это высокий заказ. Для современных компьютеров конечный характер вычислений означает, что, если я не верю результату «вычисления» конкретного компьютера, я в принципе могу выполнить конечную последовательность шагов совершенно другим способом, чтобы проверить результат. Этот вид «отката» к здравому смыслу и конечной проверке недоступен, если у нас есть сомнения относительно гиперкомпьютера.
источник
В то время как кажется довольно трудным доказать тезис Черча-Тьюринга из-за неформальной природы «эффективно вычисляемой функции», мы можем себе представить, что это значит опровергнуть. А именно, если бы кто-то создал устройство, которое (надежно) вычисляло функцию, которая не может быть вычислена ни одной машиной Тьюринга, это опровергло бы тезис Черча-Тьюринга, поскольку оно установило бы существование эффективно вычисляемой функции, которая не вычислима машиной Тьюринга.
источник
Опровержение тезиса Черча-Тьюринга представляется крайне маловероятным и концептуально очень трудно представить. Существуют различные «гипотетические физические миры», которые находятся в некотором противоречии с тезисом Черча-Тьюринга (но противоречат ли они самому себе - интересный философский вопрос). В работе Питовского "Тезис физической церкви и физическая вычислительная сложность", Iyun 39, 81-99 (1990) рассматриваются такие гипотетические физические миры. См. Также статью Итамара Питовски и Орона Шагрира: « Тезис Тьюринга и гиперкомпьютеры», Minds and Machines 13, 87-101 (2003). Орон Шагрир написал несколько философских статей о тезисе Черча-Тьюринга, см. Его веб-страницу . (Смотрите также этот пост в блоге .)
Эффективный или действенный тезис Черча-Тьюринга является бесконечно более сильным утверждением, чем первоначальное утверждение Черч-Тьюринга, в котором утверждается, что каждое возможное вычисление может быть эффективно смоделировано машиной Тьюринга. Квантовые компьютеры действительно покажут, что эффективный тезис Черча-Тьюринга недействителен (по модулю некоторых математических гипотез вычислительной сложности и по модулю «асимптотической интерпретации»). Я думаю, что эффективная гипотеза Черча-Тьюринга была впервые сформулирована Вольфрамом в 1985 году, эта статья цитируется в статье Питовского, связанной выше. На самом деле, вам даже не нужны универсальные квантовые компьютеры, чтобы опровергнуть эффективный тезис КТ, и интересным направлением исследований (которое Ааронсон среди других изучает) предложить как можно более простую демонстрацию вычислительного превосходства квантовых систем.
Это также интересная проблема, если существуют более простые способы продемонстрировать вычислительное превосходство квантовых компьютеров при наличии шума, нежели иметь полноценную квантовую отказоустойчивость (которая допускает универсальные квантовые вычисления). (Скотт А. действительно заинтересован и в этой проблеме.)
источник
Насколько я понимаю, «невозможность» доказательства или опровержения тезиса состоит в том, что не существует формального определения «эффективно вычисляемого». Сегодня мы считаем его «вычислимым на машине Тьюринга», но этот вопрос, скорее, напрашивается.
Были изучены модели вычислений, которые являются строго более мощными, чем машина Тьюринга, посмотрите на http://en.wikipedia.org/wiki/Hypercomputation для некоторых примеров. Или просто возьмите машину Тьюринга с оракулом для решения проблемы остановки машин Тьюринга. У такой машины будет своя собственная проблема остановки, но она вполне может решить исходную проблему остановки. Конечно, у нас нет такого оракула, но нет ничего математически невозможного в идее.
источник
Несоответствия гиперкомпьютеров обычно предполагают правильность границы Бекенштейна, которая устанавливает конкретное ограничение на количество информации, которое может содержать конечное количество пространства. Существует спор по поводу этой границы, но я думаю, что большинство физиков принимают это.
Если граница Бекенштейна сильно нарушена, и нет ограничения на количество информации, содержащейся в конкретной области (скажем, черная дыра или бесконечно точная и надежная гравировка), и существуют произвольно обновляемые механизмы для проверки содержимого этого область (скажем, путем тщательного изучения излучения, испускаемого, когда тщательно сконструированный объект падает в черную дыру, или путем пера над канавками гравюры), можно предположить, что уже существует артефакт, который кодирует остановившегося оракула ,
Все это очень маловероятно, но оно показывает, что утверждение о невозможности гиперкомпьютера не является математической истиной, а основано на физике. Это значит, что Андрей прав, когда говорит, что мы можем представить, что бы это значило опровергнуть (тезис Черча-Тьюринга). А именно, если кто-то создал устройство, которое (надежно) вычислило функцию, которая не может быть вычислена ни одной машиной Тьюринга .
источник
Относительно расширенного тезиса Черча-Тьюринга (подразумеваемого как «вероятностная машина Тьюринга может эффективно моделировать любую физически вычислимую функцию»):
Одна возможность - это различие между классическими и квантовыми компьютерами. В частности, вопрос "Есть ли задача, которую могут выполнять квантовые компьютеры, а классические - нет?" Недавний доклад СЦКК Скотта Ааронсона (см. Гипотезу 9 на стр. 5) выдвигает на первый план гипотезу, которая, если она будет доказана, послужит убедительным доказательством против расширенного тезиса Церкви-Тьюринга.
Если опровергнуть расширенный тезис Церкови-Тьюринга, это может выглядеть так, в частности, путем демонстрации эффективно вычисляемой задачи, которую (классическая) машина Тьюринга не может эффективно вычислить.
источник
Новая статья, представленная на DCM2011 : формализация и доказательство расширенного тезиса Церковного Тьюринга (Нахум Дершовиц и Евгения Фалькович)
источник
Следующие документы Селима Акла могут представлять интерес и иметь отношение к обсуждению:
Акл С.Г. «Три контрпримеры, чтобы развеять миф об универсальном компьютере», Parallel Processing Letters, Vol. 16, № 3, сентябрь 2006 г., с. 381 - 403.
Акл С.Г. «Даже ускоряющие машины не универсальны», Международный журнал нетрадиционных вычислений, Vol. 3, № 2, 2007, с. 105 - 121.
Надь М., Акл С.Г. «Параллелизм в квантовой обработке информации побеждает универсальный компьютер». Параллельная обработка писем. Специальный выпуск по нетрадиционным вычислительным задачам. 17, № 3, сентябрь 2007 г., с. 233 - 262.
Вот аннотация первого:
Показано, что концепция Универсального Компьютера не может быть реализована. В частности, представлены экземпляры вычислимой функции F, которые не могут быть вычислены ни на одной машине U, способной выполнять только конечное и фиксированное число операций на шаг. Это остается верным, даже если машина U наделена бесконечной памятью и способностью связываться с внешним миром, когда она пытается вычислить F. Это также остается верным, если, кроме того, U предоставляется неопределенное количество времени для вычисления F. Этот результат применим не только к идеализированным моделям вычислений, таким как машина Тьюринга и т.п., но также ко всем известным компьютерам общего назначения, включая существующие обычные компьютеры (как последовательные, так и параллельные), а также предполагаемые нетрадиционные компьютеры, такие как как биологические и квантовые компьютеры.
источник
Как это может быть правдой? Классический компьютер не может эффективно имитировать квантовый компьютер. Существуют квантовые алгоритмы, которые обеспечивают экспоненциальное ускорение по сравнению с классическими компьютерами, работающими на классических алгоритмах: алгоритм Шора - один.
источник