Что будет означать опровержение тезиса Черча-Тьюринга?

83

Извините за запоминающееся название. Я хочу понять, что нужно сделать, чтобы опровергнуть тезис Черча-Тьюринга? Где-то я читал, что это математически невозможно сделать! Почему?

Тьюринг, Россер и т. Д. Использовали разные термины, чтобы различать: «что можно вычислить» и «что можно вычислить с помощью машины Тьюринга».

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

Итак, тезис Черча-Тьюринга можно сформулировать так: каждая эффективно вычисляемая функция является вычислимой.

Итак, еще раз, как будет выглядеть доказательство, если опровергнуть эту гипотезу?

Андраш Саламон
источник
1
Проверьте приложение в этой замечательной (но трудно читаемой) статье Л. Левина arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf
user2471,

Ответы:

5

Тезис Черча-Тьюринга был доказан для всех практических целей.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Дершовиц и Гуревич, Бюллетень символической логики, 2008.

(Эта ссылка обсуждает историю работы Чёрча и Тьюринга и выступает за разделение «тезиса Чёрча» и «тезиса Тьюринга» как отдельных логических утверждений, а затем доказывает их обоих в рамках интуитивной аксиоматизации вычислимости.)

Аарон Стерлинг
источник
24
Я немного обеспокоен этим ответом. Люди могут создать неправильное впечатление, что тезис Черча-Тьюринга был доказан, хотя на самом деле это не так (и я думаю, что большинство людей думают, что это невозможно доказать).
Эмиль
5
Это будет мой последний комментарий, но я думаю, что вы, возможно, захотите спросить, почему такой сайт необходим, если все, что нам нужно сделать, это посмотреть на учебники. Арора и Барак - великие исследователи, но они не логики и не исследователи теории сложности (они все равно написали книгу о сложности, хотя это и не было их основной областью исследований), или эксперты по семантике языка программирования (что было исходной мотивацией для абстрактные автоматы). Обычная мудрость не обязательно верна, и, в конце концов, мы должны думать сами.
Аарон Стерлинг
8
Если Дершовиц и Гуревич доказали тезисы Черча и Тьюринга, то они также доказали, что в будущем мы не сможем построить компьютер, который выполняет бесконечно много вычислительных шагов за конечное время, см., Например, arxiv.org/abs/gr-qc/ 0104023, где обсуждаются такие возможности.
Андрей Бауэр
50
Как обычно понимается, тезис Черча-Тьюринга не является формальным утверждением, которое можно доказать. Это научная гипотеза, поэтому ее можно «опровергнуть» в том смысле, что она фальсифицируется. Любое «доказательство» должно содержать определение вычислимости вместе с ним, и доказательство только так же хорошо, как это определение. Я уверен, что у Дершовица-Гуревича есть прекрасное доказательство, но реальная проблема заключается в том, действительно ли определение охватывает все вычислимое. Отвечая "это может быть опровергнуто?" высказывание "это было доказано" вводит в заблуждение. Это было доказано при разумном (фальсифицируемом!) Определении вычислимости.
Райан Уильямс
47
В статье Дершовица-Гуревича ничего не говорится о вероятностных или квантовых вычислениях. Он записывает набор аксиом о вычислениях и доказывает тезис Черча-Тьюринга, принимая эти аксиомы. Однако нам осталось обосновать эти аксиомы. Ни вероятностные, ни квантовые вычисления не охватываются этими аксиомами (они допускают это для вероятностных вычислений и вообще не упоминают квантовые вычисления), поэтому мне совершенно ясно, что эти аксиомы на самом деле ложны в реальном мире, хотя Церковь-Тьюринг Тезис, вероятно, верно.
Питер Шор
60

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

Предположим, что, как предполагает Андрей, кто-то создает устройство, которое надежно вычисляет функцию которая не может быть вычислена ни одной машиной Тьюринга. Откуда нам знать, что машина на самом деле вычисляет ?фff

Очевидно, что конечного числа входных / выходных значений будет недостаточно, чтобы продемонстрировать, что машина вычисляет в отличие от некоторой другой вычислимой по Тьюрингу функции, которая согласуется с на этом конечном множестве. Следовательно, наша вера в то, что машина вычисляет , должна основываться на наших физических теориях о том, как машина работает. Если вы посмотрите на некоторые конкретные предложения для гиперкомпьютеров, вы обнаружите, что, конечно же, они берут какую-то фантастическую передовую физическую теорию и экстраполируют эту теорию на бесконечностьф фfff, Хорошо, хорошо, но теперь предположим, что мы создаем гиперкомпьютер и спрашиваем его, остановится ли когда-нибудь машина Тьюринга, которая ищет противоречие в ZFC. Предположим далее, что гиперкомпьютер отвечает «Нет». На чем мы заключаем? Делаем ли мы вывод, что гиперкомпьютер «вычислил» согласованность ZFC? Как мы можем исключить возможность того, что ZFC на самом деле несовместим, и мы только что провели эксперимент, который подделал нашу физическую теорию?

Важной особенностью определения Тьюринга является то, что его философские предположения очень слабы. Он предполагает, как и положено, определенные простые особенности нашего повседневного опыта, такие как базовая стабильность физического мира и способность выполнять конечные операции надежным, воспроизводимым и проверяемым образом. Эти вещи каждый принимает (за пределами классной комнаты философии, то есть!). Однако принятие гиперкомпьютера, похоже, требует от нас бесконечной экстраполяции.физической теории, и весь наш опыт работы с физикой научил нас не быть догматичными в отношении обоснованности теории в режиме, который намного превосходит то, что мы можем экспериментально проверить. По этой причине мне кажется крайне маловероятным, что когда-либо возникнет какой-либо всепоглощающий консенсус в отношении того, что любой конкретный гиперкомпьютер просто вычисляет, а не гиперкомпьютирует , т. Е. Делает что-то, что можно назвать «вычислением», только если вы принимаете некоторые противоречивые философские или физические предположения о бесконечных экстраполяциях.

Иными словами, для опровержения тезиса Черча-Тьюринга необходимо не только создать устройство, которое описывает Андрей, но и доказать всем, что устройство работает так, как рекламируется. Хотя это и немыслимо, это высокий заказ. Для современных компьютеров конечный характер вычислений означает, что, если я не верю результату «вычисления» конкретного компьютера, я в принципе могу выполнить конечную последовательность шагов совершенно другим способом, чтобы проверить результат. Этот вид «отката» к здравому смыслу и конечной проверке недоступен, если у нас есть сомнения относительно гиперкомпьютера.

Тимоти Чоу
источник
1
Тим, очевидно, тезис Черча-Тьюринга может быть опровергнут успешной демонстрацией модели эффективных вычислений, которая выходит за рамки общих эквивалентных моделей, определенных Черчом и Тьюрингом. Можно поспорить, насколько это невероятно, но я верю, что это все еще нужно. (Обратите внимание, что я избегаю «доказать» и «опровергнуть» в этом контексте.)
orcmid
2
@Neel: Вы не понимаете мою точку зрения. Я говорю, что если Physical Computer X выполняет вычисления, включающие n шагов, то в принципе я могу проверить вычисления, выполнив n шагов таким образом, который не опирается на причудливые физические теории. Правда, я не могу выполнить шагов, но и Физический компьютер X не может, так что это не имеет значения для моей точки зрения. 22250
Тимоти Чоу
6
@Neel: Напротив, я хочу сказать, что совершенно разумно сомневаться в причудливой физике, лежащей в основе компьютера, существующего сегодня или гиперкомпьютера будущего. Основная причина, по которой мы терпим современные компьютеры, заключается в том, что перед ними стоят конечные вычисления, которые мы в принципе можем имитировать, не прибегая к физике. Но создайте гиперкомпьютер, правильность которого по своей природе основана на бесконечной экстраполяции физических теорий за пределы экспериментально доступных режимов, и у нас нет никакого способа сказать, правильны ли вычисления или наши теории ошибочны.
Тимоти Чоу
6
@orcmid: физика должна где-то ввести картинку; иначе что мешает нам объявить, что все функции вычислимы? Чтобы заслужить имя, «вычисление» должно быть чем-то, что мы можем предусмотреть на самом деле. Вот почему предложения для гиперкомпьютеров делают все возможное, чтобы объяснить, как они могут быть сконструированы физически. Моя точка зрения заключается в том, что мы должны сделать мысленный эксперимент еще дальше: столкнувшись с предполагаемым гиперкомпьютером, как бы мы узнали, что он действительно работает так, как рекламируется? Если бы мы не могли знать, то действительно ли было бы правомерно называть его результаты «вычислениями»?
Тимоти Чоу
1
Это интересно, может быть, мы не можем действительно знать, что машина вычисляет f, потому что мы просто завершились по Тьюрингу. Возможно, потребуется гиперкомпьютерный наблюдатель, чтобы проверить, действительно ли гиперкомпьютерный объект действительно гиперкомпьютерный oO
guillefix
58

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

Андрей Бауэр
источник
1
В каком смысле кто-то должен «строить» машину? Мы живем в конечном мире, который может содержать только компьютеры, которые являются более слабыми, чем машины Тьюринга. Возможно, он должен придумать вместо этого новую интуитивно привлекательную логическую характеристику? На что это может быть похоже?
Vag
2
И наша вселенная все более ограничена, чем теоретические машины конечного состояния, из-за ограниченности массы / энергии конкретной константой и пределом Бреммермана pespmc1.vub.ac.be/ASC/Bremer_limit.html, поэтому существуют вычисления, которые могут делать большие воображаемые автоматы, но не физические компьютеры не может (проблемы с вычислениями).
Vag
2
Разумеется, человеку необходимо иметь возможность моделировать машину, чтобы опровергнуть первоначальный тезис Тьюринга, который идентифицирует эффективную вычисляемость и вычислимость человека.
Карл Маммерт,
35

Опровержение тезиса Черча-Тьюринга представляется крайне маловероятным и концептуально очень трудно представить. Существуют различные «гипотетические физические миры», которые находятся в некотором противоречии с тезисом Черча-Тьюринга (но противоречат ли они самому себе - интересный философский вопрос). В работе Питовского "Тезис физической церкви и физическая вычислительная сложность", Iyun 39, 81-99 (1990) рассматриваются такие гипотетические физические миры. См. Также статью Итамара Питовски и Орона Шагрира: « Тезис Тьюринга и гиперкомпьютеры», Minds and Machines 13, 87-101 (2003). Орон Шагрир написал несколько философских статей о тезисе Черча-Тьюринга, см. Его веб-страницу . (Смотрите также этот пост в блоге .)

Эффективный или действенный тезис Черча-Тьюринга является бесконечно более сильным утверждением, чем первоначальное утверждение Черч-Тьюринга, в котором утверждается, что каждое возможное вычисление может быть эффективно смоделировано машиной Тьюринга. Квантовые компьютеры действительно покажут, что эффективный тезис Черча-Тьюринга недействителен (по модулю некоторых математических гипотез вычислительной сложности и по модулю «асимптотической интерпретации»). Я думаю, что эффективная гипотеза Черча-Тьюринга была впервые сформулирована Вольфрамом в 1985 году, эта статья цитируется в статье Питовского, связанной выше. На самом деле, вам даже не нужны универсальные квантовые компьютеры, чтобы опровергнуть эффективный тезис КТ, и интересным направлением исследований (которое Ааронсон среди других изучает) предложить как можно более простую демонстрацию вычислительного превосходства квантовых систем.

Это также интересная проблема, если существуют более простые способы продемонстрировать вычислительное превосходство квантовых компьютеров при наличии шума, нежели иметь полноценную квантовую отказоустойчивость (которая допускает универсальные квантовые вычисления). (Скотт А. действительно заинтересован и в этой проблеме.)

Гил Калай
источник
Я думал, что машины Тьюринга могут моделировать квантовые компьютеры? (С большой потерей эффективности, конечно.) (Правка: ах, я заметил, вы сказали, что «тезис об эффективной КТ» - это тот тезис, что ТМ могут эффективно имитировать любое вычислительное устройство?)
Эмиль
5
Я думаю, что Гил говорит о «расширенном» тезисе Черча-Тьюринга (который он называет «эффективным» тезисом Черч-Тьюринга) о том, что все эффективно вычислимое в природе также вычислимо на машине Тьюринга с многопоточностью.
Райан Уильямс
2
Я добавил предложение, чтобы уточнить это.
Гил Калай
Гил, спасибо за этот прекрасный пост! Чтобы выразить точку зрения разработки квантовых систем, мы, люди, существуем в шумной вселенной, в которой (без коррекции ошибок) ЭСТ эмпирически верна - в том, что квантовые динамические процессы могут быть эффективно смоделированы - посредством формализмов, в которых (эффективно) квантовая суперпозиция является локальным приближением, во многом в том же смысле, что евклидова геометрия является локальным приближением к римановой геометрии. Охватывает ли природа подобные квантовые потоки, чтобы эффективно вычислять себя? Это открытый вопрос ... и очень интересный ИМХО.
Джон Сидлес
Вдохновленный постом Джила и постом Тимоти Чоу (ниже), я повысил вышеупомянутый комментарий до официального вопроса TCS: «Какова надлежащая роль валидации в квантовом отборе, моделировании и тестировании расширенной Церковью-Тьюринга (ECT)? " Спасибо, Гил и Тимоти.
Джон Сидлес
24

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

Были изучены модели вычислений, которые являются строго более мощными, чем машина Тьюринга, посмотрите на http://en.wikipedia.org/wiki/Hypercomputation для некоторых примеров. Или просто возьмите машину Тьюринга с оракулом для решения проблемы остановки машин Тьюринга. У такой машины будет своя собственная проблема остановки, но она вполне может решить исходную проблему остановки. Конечно, у нас нет такого оракула, но нет ничего математически невозможного в идее.

Евгений Торстенсен
источник
Спасибо за ответ. Итак, разработка функции, которая математически реализуема (но не физически) некоторой моделью, но не машиной Тьюринга, не опровергает этот тезис?
1
Дершовиц и Гуревич 2008 аксиоматизируют «эффективно вычисляемый» с использованием абстрактных автоматов.
Аарон Стерлинг
4
Итак, они определяют другую вычислительную модель и доказывают, что она эквивалентна существующей, не так ли? Почему эта вычислительная модель более надежна, чем существующие?
Blaisorblade
Мы могли бы использовать человеческую силу как оракула, придумав формальное доказательство (не) прекращения. Плохое время выполнения, хотя ...
Рафаэль
10

Несоответствия гиперкомпьютеров обычно предполагают правильность границы Бекенштейна, которая устанавливает конкретное ограничение на количество информации, которое может содержать конечное количество пространства. Существует спор по поводу этой границы, но я думаю, что большинство физиков принимают это.

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

Все это очень маловероятно, но оно показывает, что утверждение о невозможности гиперкомпьютера не является математической истиной, а основано на физике. Это значит, что Андрей прав, когда говорит, что мы можем представить, что бы это значило опровергнуть (тезис Черча-Тьюринга). А именно, если кто-то создал устройство, которое (надежно) вычислило функцию, которая не может быть вычислена ни одной машиной Тьюринга .

Чарльз Стюарт
источник
Граница Бекенштейна может иметь место, но гиперкомпьютер все еще возможен.
Андрас Саламон
@ Андрас: В принципе, да: нам нужно гораздо больше физической теории, чтобы заставить отрицательный аргумент работать. Но попытки «описать» гиперкомпьютерные механизмы, которые я видел, все это нарушают.
Чарльз Стюарт
Нарушают ли границы те, которые включают замкнутые петли вблизи черных дыр?
Андрас Саламон
@ Андрас: Я не знаю, какие из них вы имеете в виду. Теория струн в целом совместима с оценкой Бекенштейна.
Чарльз Стюарт
Я имею в виду такие вещи, как arxiv.org/abs/gr-qc/0209061, которые вместо того, чтобы полагаться на теорию струн, «просто» предполагают, что можно отправлять вычисления в прошлое.
Андрас Саламон
9

Относительно расширенного тезиса Черча-Тьюринга (подразумеваемого как «вероятностная машина Тьюринга может эффективно моделировать любую физически вычислимую функцию»):

Одна возможность - это различие между классическими и квантовыми компьютерами. В частности, вопрос "Есть ли задача, которую могут выполнять квантовые компьютеры, а классические - нет?" Недавний доклад СЦКК Скотта Ааронсона (см. Гипотезу 9 на стр. 5) выдвигает на первый план гипотезу, которая, если она будет доказана, послужит убедительным доказательством против расширенного тезиса Церкви-Тьюринга.

Если опровергнуть расширенный тезис Церкови-Тьюринга, это может выглядеть так, в частности, путем демонстрации эффективно вычисляемой задачи, которую (классическая) машина Тьюринга не может эффективно вычислить.

Даниэль Апон
источник
2
Чтобы уточнить, квантовые вычисления только ставят под сомнение тезис Эффективного / Расширенного / Сильного Церковного Тьюринга, в котором говорится, что все реализуемые модели вычислений могут быть смоделированы на машине Тьюринга за полиномиальное время. Обычный тезис Черча-Тьюринга не накладывает ограничений на эффективность. Квантовые компьютеры не надеются свергнуть эту версию, потому что машина Тьюринга может просто моделировать все экспоненциально-многочисленные ветви квантовых вычислений за конечное время.
Ян
Да, спасибо вам за это - я исправил неаккуратное использование двух терминов.
Даниэль Апон
Хммм ... но согласно стандартным определениям, разве ДЭХ уже не был окончательно опровергнут? Алиса: «Вот образец действительно случайных двоичных цифр, вычисленных моей (одномодовой) квантовой оптической сетью». Боб: «Вот образец псевдослучайных цифр, вычисленных на классической машине Тьюринга». Алиса: «Извините, Боб ... ваш образец сжимается алгоритмически, а мой - нет. Поэтому мои данные показывают, что ECT неверен!» Формально говоря, рассуждения Алисы безупречны. Тем не менее, в отсутствие проверочных проверок утверждений Алисы, должны ли мы быть удовлетворены?
Джон Сидлес
4

Следующие документы Селима Акла могут представлять интерес и иметь отношение к обсуждению:

Акл С.Г. «Три контрпримеры, чтобы развеять миф об универсальном компьютере», 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. Этот результат применим не только к идеализированным моделям вычислений, таким как машина Тьюринга и т.п., но также ко всем известным компьютерам общего назначения, включая существующие обычные компьютеры (как последовательные, так и параллельные), а также предполагаемые нетрадиционные компьютеры, такие как как биологические и квантовые компьютеры.

Массимо Кафаро
источник
Можете ли вы предоставить ссылку на первый документ, который не находится за платным доступом? Каково их определение «вычислимой функции»? Согласно стандартному определению (есть машина Тьюринга, которая вычисляет функцию), их утверждение по определению ложно ...
Кристофер Монсанто
Я только что отправил вам газету по электронной почте.
Массимо Кафаро
Вот одна из этих статей: research.cs.queensu.ca/home/akl/techreports/even.pdf . Подробнее здесь: research.cs.queensu.ca/Parallel/projects.html . В статье нет фактического определения «компьютер», только волнообразное описание. Предположительно, это волнообразное описание может быть формализовано с небольшим количеством работы, используя модель машины Тьюринга или что-то подобное в качестве основы.
Сашо Николов
W(t)tcW(t)>ct
Сашо Николов
-6

Как это может быть правдой? Классический компьютер не может эффективно имитировать квантовый компьютер. Существуют квантовые алгоритмы, которые обеспечивают экспоненциальное ускорение по сравнению с классическими компьютерами, работающими на классических алгоритмах: алгоритм Шора - один.

Роберт МакГвайер
источник
3
1) Может быть классический алгоритм разложения множителей. Мы не знаем ни одного, но его существование полностью согласуется с состоянием теории сложности. 2) Оригинальный тезис Черча-Тьюринга касается вычислимости, а не эффективной вычислимости.
Сашо Николов