Теоретические машины, более мощные, чем машины Тьюринга

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

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

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

Скотту Ааронсону, вероятно, есть что сказать по этому поводу - я позволю вам разобраться с этим самостоятельно.

Да, есть теоретические машины, которые превосходят машины Тьюринга по вычислительной мощности, такие как машины Oracle и бесконечное время Тьюринга машина . Модное слово, которое вы должны передать Google, - это гиперкомпьютеры .

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

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

В этом отношении его можно сравнить с евклидовой геометрией. Является ли наша вселенная по своей сути евклидовой? Почему наши методы измерения земли ограничены ее принципами? Разве у нас не может быть гипергеометрии, которая позволяет более мощные измерения земли? Ответ таков: мы можем и делаем, но мы не всегда называем результаты «измерение земли» или «геометрия».

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

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

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

$\Pi_2^0$ предложений, объяснив , что я не уверен о том , как отделить конечные входы от бесконечных входов, и , следовательно , не уверен , является ли Количественным над входами хорошо определено. Это оправдание возникло из разговора с другим Томасом, а именно с Томасом Чустом.)