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

39

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

user1561358
источник
5
Такие вопросы, как "является ли X определяющими характеристиками нашей ( sic ) вселенной?" это вопрос физики, поскольку физика - это в точности изучение «законов вселенной». Информатика - это математические объекты, которые иногда реализуются физическими средствами.
Бакуриу
2
Я бы порекомендовал изучить «машины супер-тьюринга», особенно те, которые предложены Have Siegelmann : umass.edu/newsoffice/article/… и binds.cs.umass.edu/papers/1995_Siegelmann_Science.pdf
nobillygreen,
1. Просим вас задавать только один вопрос на пост, пожалуйста. Если у вас есть другие вопросы, вы можете опубликовать их отдельно, после просмотра ответов на них. Кроме того, вопросы об определяющих характеристиках нашей вселенной - это вопросы физики, и они здесь не по теме. Я редактирую дополнительные вопросы, чтобы помочь вам сосредоточиться на одном вопросе. Вы можете опубликовать их отдельно (см. Историю изменений, чтобы найти их снова). 2. Какие исследования вы провели? о чем ты думаешь? Вопрос из одного предложения слишком короткий. Попытайтесь отредактировать это, чтобы уточнить это; это поможет дать вам лучшие ответы.
DW
3. «Можем ли мы предположить, что…» - нет, конечно, нет. Почему вы думаете, что можете это принять? Вы не можете просто предположить что-то, потому что было бы хорошо, если бы это было правдой, или кажется, что это могло бы быть правдой, или потому что мы не сразу видим причину, почему это было бы ложно. Информатика - это доказательство, а не просто предположение. Какой у тебя настоящий вопрос?
DW

Ответы:

26

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

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

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

Юваль Фильмус
источник
На самом деле у меня есть блог Скоттс уже в закладки. :) В любом случае, поскольку тезис КТ все еще актуален (если что-то не произошло, о чем я не знаю), все, что остается, - это поговорить об определении вычислимости или найти машину, которая каким-то образом опровергает КТ.
user1561358
3
«Как обсуждалось в этом эссе, теория сложности к настоящему времени вышла далеко за пределы детерминированных машин Тьюринга, чтобы включить (например) квантовую механику, параллельные и распределенные вычисления и случайные процессы, такие как дарвиновская эволюция». ( Почему философы должны заботиться о вычислительной сложности , Скотт Ааронсон , стр. 49)
reinierpost
1
Я думаю также примечательно, что квантовые компьютеры не ускоряют произвольную задачу AFAIK. И они «только» ускоряют его максимум на 2 ^ N, где N - количество квантовых битов.
Надеюсь, что это
13

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

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

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

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

reinierpost
источник
Под «вычислением одним процессором, выполняющим шаги строго последовательно без внешних помех», вы подразумеваете, что если компьютер имеет внешние помехи или может работать параллельно, он гораздо более мощный, чем машина Тьюринга?
кейт
1
Не совсем. Если все, что вы хотите знать, это то, какие сопоставления от конечных входов до конечных выходов могут быть вычислены, то добавление их не даст вам больше возможностей: вы не сможете вычислить больше отображений, чем раньше.
reinierpost
5

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

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

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

Томас Климпел
источник