Расширенный тезис Церковного Тьюринга

35

Одним из наиболее обсуждаемых вопросов на сайте было « Что бы это значило, чтобы опровергнуть тезис Церковного Тьюринга» . Отчасти это связано с тем, что Дершовиц и Гуревич опубликовали доказательство тезиса Черч-Тьюринга - Бюллетень символической логики в 2008 году. (Я не буду обсуждать это здесь, но для ссылки и подробных комментариев, пожалуйста, смотрите оригинальный вопрос, или - - бесстыдная самореклама - запись в блоге, которую я написал.)

Этот вопрос о расширенном тезисе Черч-Тьюринга, который, как сформулировал Ян Парберри, таков:

Время на всех «разумных» моделях машин связано многочленом.

Благодаря Джорджо Маринелли, я узнал , что один из соавторов предыдущей статьи, Дершовицем, и аспирантка его, Фальковича, уже опубликовал доказательство Расширенного Тезис Черча-Тьюринга, которая только что появилась в мастерской разработки Вычислительные модели 2011 .

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

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

Итак, мой вопрос: действительно ли это "широко распространено" даже в случае "действительно" последовательных вычислений без рандомизации? Что делать, если все случайно? Квантовые вычисления были бы вероятным контрпримером, если на самом деле их можно было бы реализовать, но есть ли возможности, более «слабые», чем квантовые, которые также были бы контрпримерами?

Аарон Стерлинг
источник
1
Было много дискуссий по поводу дерандомизации или исключения случайных компонентов случайных алгоритмов. Например, см. ( Bit.ly/rjx5YZ ) Я однажды задал вопрос Лэнсу Фортнау в теории Среднего Запада о деквантовании, и это было бессмысленно. Но это вызвало здесь хорошее обсуждение ( bit.ly/nT0BnK ). Но есть и более плодотворные возможности. Пример более слабой возможности, связанной с квантовыми алгоритмами, приведен лауреатом премии Лесли Валианта Тьюринга 2011 года ( bit.ly/nSyffN ).
Джошуа Герман
1
@ Джошуа, ACM только что опубликовал Лекцию Тьюринга Valiant 2011 года (URL: awards.acm.org/… ); это стоит посмотреть С прикладной точки зрения см. Недавние статьи Илья Купрова с соавторами в JMR: Алгоритм полиномиального масштабирования спиновой динамики, основанный на адаптивном ограничении пространства состояний, и полиномиальный масштаб спиновой динамики. II: Дальнейшее сжатие пространства состояний с использованием методов подпространства Крылова и исключения нулевых треков . Эта медленная конвергенция «чистого» и «прикладного» CT / QIT практически важна и доставляет массу удовольствия.
Джон Сидлес

Ответы:

44

Подготовительный Рант

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

Это было ясно уже с оригинальной компьютерной томографией, но с ECT это стало еще яснее, поскольку ECT не только «философски недоказуем», но сегодня многие считают его ложным! Для меня квантовые вычисления - это огромный, вопиющий контрпример, который должен стать отправной точкой для любой современной дискуссии о ДЭХ, а не чем-то отвлеченным. Тем не менее, статья Дершовица и Фальковича даже не касается КК до последнего абзаца:

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

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

Теперь на ваши (интересные) вопросы!

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

Рандомизация, вероятно, не бросает вызов ДЭХ, как это принято понимать, из-за убедительных доказательств того, что P = BPP сегодня. (Хотя учтите, что если вас интересуют параметры, отличные от проблем с языковым решением - например, реляционные проблемы, деревья решений или сложность связи), то рандомизация может иметь огромное значение. И эти параметры вполне разумны о которых можно говорить; они просто не те, о которых люди обычно думают, когда обсуждают ДЭХ.)

Другой класс "контрпримеров" к ECT, который часто используется, включает аналоговые или "гипер" вычисления. Я считаю, что, по нашему лучшему современному пониманию физики, аналоговые вычисления и гиперкомпьютеры не могут масштабироваться, и причина, почему они не могут, по иронии судьбы, заключается в квантовой механике! В частности, хотя у нас еще нет квантовой теории гравитации, то, что известно сегодня, предполагает, что существуют фундаментальные препятствия для выполнения более чем 10 43 шагов вычисления в секунду или разрешения расстояний меньше, чем примерно 10 -33 см.

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

Что касается вашего последнего вопроса:

    Квантовые вычисления были бы вероятным контрпримером, если на самом деле их можно было бы реализовать, но есть ли возможности, более «слабые», чем квантовые, которые также были бы контрпримерами?

Сегодня существует множество интересных примеров физических систем, которые, кажется, способны реализовать некоторые квантовые вычисления, но не все из них (давая классы сложности, которые могут быть промежуточными между BPP и BQP). Кроме того, многие из этих систем проще реализовать, чем полный универсальный контроль качества. Посмотрите, например, эту статью Бремнера, Йозсы и Шепарда или эту статью Архипова и меня.

Скотт Ааронсон
источник
3
О «доказательстве». Я считаю, что исследовательская программа Дершовица и др. Пытается создать «ZF для алгоритмов», чтобы аксиоматизировать интуитивное понятие «алгоритм». Тогда мы можем поспорить, следует ли включать выбор или детерминированность или существование большого кардинала - какими бы ни были компьютерные аналоги этих вещей. Я действительно полагаю, что способ представления этой аксиоматизации основан на результатах («посмотрите, мы можем доказать этот знаменитый тезис»), но авторы тезисной статьи действительно пытаются представить историческое обоснование своих предположений.
Аарон Стерлинг
1
@ Scott Aaronson Интересный и яркий взгляд на КК. Просто любопытно. Что нужно сделать, чтобы показать, что КК не может быть контрпримером?
против
10
Вы имеете в виду, показать КК невозможно? По крайней мере, это потребовало бы серьезного пересмотра нашего понимания квантовой механики. Это может означать открытие какой-то новой физической теории, которая заменила QM (и так случилось, чтобы восстановить BPP в качестве предела вычислений), или некоторого пока еще не открытого принципа, действующего «поверх» или «рядом» с QM, который запрещал QC. В любом случае, Нобелевские премии! :)
Скотт Ааронсон
Понравился твой комментарий. Нужно будет больше копать на КК. Я очень наивен в этой теме.
против
1
Еще одна интересная квантовая модель между полными квантовыми вычислениями и классическими - это модели на основе квантовых разногласий, такие как DQC1.
Маркос Вильягра
5

Этот ответ предназначен в качестве дополнения к ответу Скотта Ааронсона (с чем я в основном согласен).

С инженерной точки зрения поразительно, что в статье Дершовица / Фальковича слово «случайный» используется только в смысле «оперативной памяти», и, кроме того, в статье не используется слово «образец» (или какое-либо варианты) вообще. Скорее, фокус анализа Дершовица / Фальковича ограничивается исключительно вычислением числовых функций.

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

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

Будет ли эта обобщенная до выборки версия ДЭХ по-прежнему входить в сферу компетенции TCS, как это традиционно предполагалось? Ответ, по-видимому, "да", в соответствии с часто задаваемыми вопросами по TCS Stack Exchange :

Мы отсылаем вас к описанию ACM Special Interest Group по алгоритмам и теории вычислений (SIGACT) ... TCS охватывает широкий спектр тем, включая вероятностные вычисления ... Работа в этой области [TCS] часто отличается акцентом на математические техника и строгость.
Эти соображения предполагают, что для того, чтобы иметь отношение к практическим вычислениям STEM, анализ ECT должен включать явные соображения по проверке и проверке выборки ... и мы можем разумно ожидать, что это расширение ECT будет связано как с красивыми математическими теоремами, так и с для стимулирования физического понимания.

Джон Сидлес
источник
0

ECTT{0,1,+,×}ECTTЭто говорит о том, что этот предикат разумности удовлетворяется именно теми моделями, которые имеют полиномиальный перевод времени на машину Тьюринга. Как аксиома, это не фальсифицируется в том смысле, что наша теория может противоречить ей, если теория была последовательной с самого начала, но обоснованность нашей теории фальсифицируема: возможно, существует разумная модель вычисления, которая не связана с Машины Тьюринга по полиномиальному времени-трансляции. Допуская, что это гипотетическое открытие может повлечь за собой сдвиг в размышлениях о том, что является разумным, именно так я вижу формальную сторону. В ретроспективе это кажется тривиальным, но я думаю, что важно отличать математику от всего остального.

ECTTBPPPECTTPBPPBPPECTTPECTTPBQPECTTECTTBPPBQPP

Например, предположим, что я утверждаю, что построил машину, которая учитывает числа и что ее среда выполнения удовлетворяет определенной полиномиальной границе. Машина находится в коробке, вы вводите число, записанное на бумажной ленте, и она распечатывает факторы. Нет сомнений в том, что это работает, так как я использовал его, чтобы выиграть вызовы RSA, конфисковать криптовалюту, учитывать большое количество по вашему выбору и т. Д. Что в коробке? Это какой-то удивительный новый тип компьютера, или это обычный компьютер, на котором работает какое-то удивительное новое программное обеспечение?

ECTTECTT

ECTTEXPTIMEPCTC=PSPACEECTTPPSPACE

PNPECTTPPCTCP=NPECTTECTTNP3SATP

EXPTIMEECTTEXPTIMEPECTT

ECTTP=BPPECTTPBQP

ECTT{}ECTT{}

ECTT

Дан Брумлев
источник
1020