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

26

Я не могу думать ни о какой такой модели, может быть, о какой-то форме типизированного лямбда-исчисления? какой-то элементарный клеточный автомат?

Это почти опровергло бы «Принцип вычислительной эквивалентности» Вольфрама:

Почти все процессы, которые не являются явно простыми, могут рассматриваться как вычисления эквивалентной сложности

automata-theory computability turing-machines lambda-calculus universal-computation Диего де Эстрада
источник

Ответы:

18

Вы можете легко создавать искусственные модели, которые не являются полными по Тьюрингу, но проблема остановки для них неразрешима. Например, возьмите все ТМ, которые не останавливаются ни на чем, кроме .0

По поводу заявления:

Вы не можете опровергнуть утверждение, которое не является достаточно точным. Почти ни одно из слов в утверждении не является четко определенным (просьба дать определение для них, если это не так).

Кава
источник
ммм, скажем, модель завершена по Тьюрингу, если она может имитировать UTM.
Диего де Эстрада
1
Я думаю, что принцип эквивалентности Вольфрама ближе к физике, чем к логике. Логики, кажется, любят атаковать его по разным причинам: это не точно, это не доказано, мы можем все устроить так, чтобы это было ложно и т. Д. Но на самом деле Вольфрам по-своему указывает на очень интересный факт о вычислениях как это возникает "в природе".
Андрей Бауэр
1
Я не знаю, как собирать вишню, книга кажется мне достаточно понятной, особенно все эти записи. Есть ли априорная причина не допускать изменений стандартных определений? Вы измеряете не с тем критерием здесь. Вольфрам не занимается математикой, по крайней мере, не в традиционном смысле этого слова.
Андрей Бауэр
4
@ Андрей, моя главная проблема в том, что утверждение настолько расплывчато, что я не понимаю, как оно может делать какие-либо поддающиеся проверке / опровержимые прогнозы. И да, если кто-то меняет стандартные определения просто для того, чтобы интерпретировать то, что не было бы поддержкой заявки, в качестве поддержки заявки, то я думаю, что это проблематично.
Каве
4
Утверждение расплывчато, но что с того? Это не логика или математика. Это наблюдение, подкрепленное толстой книгой, полной примеров, говорит о том, что в природе «вычислительные системы», как правило, либо просты, либо чрезвычайно сложны, и «эквивалентны» друг другу. Вместо того, чтобы критиковать Вольфрама за то, что он не говорит на языке логики и математики, было бы более продуктивным увидеть, что у него есть точка, а затем сформулировать эту точку в любом формализме, который пожелает ваше сердце. Но, конечно, если ваше сердце не желает ничего подобного, то вы этого не сделаете.
Андрей Бауэр
4

Я уверен, что аргумент диагонализации применим к любой модели вычислений, которая:

  • может представлять себя в виде строки, и
  • может имитировать другую машину, учитывая приведенное выше представление

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

gabgoh
источник
10
∀x.f(x)≠x
2

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

Super0
источник
-2

Вероятно. Есть много математических проблем, которые, вероятно, включают некоторые из них, которые неразрешимы, то есть ответ «да», но никаких доказательств этого не существует. Например, проблема Collatz 3x + 1 возникает в качестве кандидата. Или вопрос о том, содержит ли pi произвольно длинные строки последовательных 9-ти. Любая такая проблема может рассматриваться как «модель вычислений», предположительно намного менее мощная, чем UTM, но она все еще не может быть решена, «останавливается» ли она или «всегда останавливается».

Уоррен Д. Смит
источник
Я не думаю, что этот подход может сработать. Смотрите: для любого такого фиксированного оператора существует алгоритм, который решает, является ли он «истинным» или «ложным» за конечное время, даже когда он неразрешим в ZFC (ref: en.wikipedia.org/wiki/Busy_beaver # Приложения ). С другой стороны, если вы рассматриваете в качестве модели вычислений проблему «дано утверждение, решите, есть ли в ZFC доказательство», я думаю, что эта модель полна по Тьюрингу.
Диего де Эстрада