Может ли вероятностная машина Тьюринга решить проблему остановки?

Компьютер с бесконечным потоком действительно случайных битов является более мощным, чем компьютер без него. Вопрос: достаточно ли он силен, чтобы решить проблему остановки?

То есть может ли вероятностный компьютер определить, останавливается ли детерминированная программа?

Пример вероятностного компьютера, который делает что-то детерминированное, чего не может сделать: Рассмотрим небольшую программу (длиной менее килобайта), которая выводит строку с колмогоровской сложностью, превышающей гигабайт. Сложность Колмогоровастроки - это длина самой короткой детерминированной программы, создающей эту строку. Таким образом, по определению детерминированная программа не может создать строку, сложность которой превышает ее собственную длину. Однако при наличии бесконечного потока действительно случайных битов небольшая программа способна выполнить задачу с успехом 99,99999 ...%, просто отобразив, скажем, 10 миллиардов случайных битов и надеясь, что колмогоровская сложность этих битов достаточно высока , Следовательно, создание цепочки превосходящей колмогоровской сложности находится в пределах горизонта вероятности вероятностной программы, но совсем не возможно для детерминированной программы.

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

редактировать: я только что понял, что некоторые вещи, которые я написал, были полной ерундой, извините за это. Теперь я изменил доказательство и сделал определение вероятностной машины, которую я использую, более точным.

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

Я думаю, что мы можем определить вероятностную машину Тьюринга несколькими способами. Я буду использовать определение, которое кажется вполне естественным (и для которого работает мое доказательство;) Давайте определим вероятностную машину следующим образом: она получает дополнительную ленту, на которой записана какая-то бесконечная строка, мы говорим, что эта машина решает язык если каждый он останавливается и принимает с вероятностью , когда вероятность берется по этим дополнительным случайным строкам, а для каждого он останавливается и отклоняется с вероятностью .x ∈ L > $L$$x \in L$ x∉L>$>\frac{1}{2}$$x \not \in L$$>\frac{1}{2}$

Теперь мы покажем, что если существует такая вероятностная машина которая решает проблему остановки для детерминированных машин, мы могли бы использовать ее для построения детерминированной машины которая решает проблему остановки для детерминированных машин - и мы знаем, что такая машина не может существовать$P$$H$

Предположим, что такой существует. Мы можем построить детерминированную машину которая принимает в качестве входных данных вероятностную машину с некоторым входом , котораяM R $P$$M$$R$$x$

• останавливается и принимает, если и только если принимает (то есть останавливает и принимает более чем на половине случайных строк).x R $R$$x$$R$$x$
• останавливается и отклоняется тогда и только тогда, когда отклоняет (т.е. останавливает и отклоняет более чем на половине случайных строк).x R $R$$x$$R$$x$
• петли в противном случае

По сути, для всех имитирует на входе и на каждой строке из в качестве префикса строки на случайной лентеВ настоящее время:я ∈ 1 , 2 , . , , R x 0 , 1 i$M$$i \in 1, 2, ...$$R$$x$${{0,1}}^i$$R$

• если для префиксы длины останавливаются и принимаются, не пытаясь прочитать больше, чем битов со случайной ленты, останавливает и принимает яRя$>\frac{1}{2}$$i$ $R$$i$$M$
• если для префиксы длины останавливаются и отклоняются, не пытаясь прочитать больше, чем битов со случайной ленты, останавливает и отклоняет яRя$>\frac{1}{2}$$i$ $R$$i$$M$
• в противном случае запускает симуляцию с .i : = i + $M$$i := i+1$

Теперь мы должны убедить себя, что если принимает (отклоняет) с вероятностью , то для некоторых он будет принимать (отклонять) префиксы длина случайной строки без попыток прочитать больше, чем бит со случайной ленты. Это технически, но довольно просто - если мы примем иное, тогда вероятность принятия (отклонения) приближается к мере того, как уходит в бесконечность, поэтому для некоторых это должно быть .x p > $R$$x$ я>$p >\frac{1}{2}$$i$ яяр>$>\frac{1}{2}$$i$$i$ яяр>$p >\frac{1}{2}$$i$$i$$p >\frac{1}{2}$

Теперь мы просто определяем нашу детерминированную машину решающую проблему остановки (т.е. решаем, принимает ли данная детерминированная машина данное слово ) a как . Обратите внимание, что всегда останавливается, потому что выбор языка нашими вероятностными машинами был определен таким образом, что всегда происходит одно из этих двух:N x H ( N , x ) = M ( P ( N , x ) ) M ( P ( N , x ) $H$$N$$x$$H(N,x) = M(P(N,x))$$M(P(N, x))$

• машина останавливается и принимает более половины случайных строк
• машина останавливается и отклоняет более половины случайных строк.

Это зависит от того, что вы подразумеваете под вероятностным алгоритмом, определяющим некоторый предикат.

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

• P ( M ) принимает с ненулевой вероятностью, если M останавливается,
• P ( M ) никогда не принимает, если M не останавливается, и
• Р ( М ) останавливается с вероятностью 1 для каждого М .

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

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

• Если вам требуется, чтобы P ( M ) останавливался всегда, а не просто с вероятностью 1 , тогда ясно, что P можно моделировать детерминистическим алгоритмом. (См. Википедию для объяснения разницы между «всегда» и «с вероятностью 1.»)
• Если вы устанавливаете строгие границы ошибки, требуя, чтобы P ( M ) остановился и дал правильный ответ с вероятностью, строго превышающей 1/2, для каждого M (то есть вам все равно , не остановится ли P ( M ) или не остановится и дайте неправильный ответ в остальных случаях), тогда P можно смоделировать с помощью детерминированного алгоритма, используя аргумент, указанный в ответе Каролины Солтыс .

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

$P$$P$$P$

Я думаю, что это был смысл комментария Рафаэля.

$A\subseteq\mathbb N$$A$

де Леу К., Мур Е.Ф., Шеннон К.Е. и Шапиро Н. Вычислимость с помощью вероятностных машин. Автоматические исследования, с. 183–212. Летописи математических исследований, нет. 34. Издательство Принстонского университета, Принстон, Нью-Джерси, 1956.

Дж. Сакс, Степени неразрешимости, Издательство Принстонского университета, 1963.