Ограниченная проблема остановки разрешима. Почему это не противоречит теореме Райс?

9

Одно из утверждений о теореме Райса приведено на странице 35 «Вычислительная сложность: современный подход» (Арора-Барак):

Частичная функция от до - это функция, которая не обязательно определяется на всех ее входах. Мы говорим, что TM вычисляет частичную функцию если для каждого для которого определено , и для каждого для которого не определено, попадает в бесконечный цикл при выполнении на входе . Если - это набор частичных функций, мы определяем как булеву функцию, которая на входах выводит 1 тогда и только тогда, когда { 0 , 1 } M f x f M ( x ) = f ( x ) x f M x S f S α M α{0,1}{0,1}MfxfM(x)=f(x)xfMxSfSαMαвычисляет частичную функцию в . Теорема Райса говорит, что для любого нетривиального функция не вычислима.Sf SSfS

Википедия утверждает, что языки машин ограниченного времени ТУЗЫ полны. Я ожидаю, что этот язык выглядит примерно так: принимает менее чем за шагов . Итак, пусть это некоторый DTM, который решает этот ограниченный язык за экспоненциальное время. Кажется, что этот DTM решает какое-то свойство для ВСЕХ машин Тьюринга, поэтому моя интуиция говорит мне, что теорема Райс исключает такое решение. Но, очевидно, вычисляет общую функцию. x n } M M{(α,x,n):Mαxn}MM

Чего мне не хватает в связи между этим языком и теоремой Райс?

ttbo
источник

Ответы:

13

Язык

{(α,x,n):Mα accepts x in less than n steps}

это не набор индексов, то есть он не имеет форму

LP={MM is TM, fP. fM=f}

для некоторого множества (частично рекурсивные) функций , с (частичные) функции вычисляются TM . Теорема Райс делает утверждения только о таком ; многие «интуитивные» перефразирования не помогают. Смотрите также здесь .е М М Л РPfMMLP

Обратите внимание, что это не только техническая деталь здесь. Теорема Райса не относится к

L={MM accepts M in less than M steps} ,

или. Вы понимаете почему?

Для каждой машины в вы можете легко построить много машин , которые принимают один и тот же язык , но работать более шагов, и , таким образом , не в . Таким образом, не является индексом.M л лLMLL

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

Рафаэль
источник
+1. Особенно для гиперссылки, которая, вероятно, применима и здесь. Тем не менее, я все равно попытался дать «интуитивный» анализ в качестве альтернативного ответа.
Йирка Ханика
6

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

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

Джирка ханика
источник
5

Во-первых, слова на вашем языке не являются кодировками машин, они содержат больше информации, поэтому вы не можете напрямую применять теорему Райса. Тем не менее, теорема Райса говорит о невозможности рассуждения о функции, вычисляемой машиной Тьюринга (а именно, лежит ли она в некотором множестве ). Это не тот случай, поскольку, как упоминал Рафаэль, существуют две машины которые вычисляют одну и ту же функцию, но одна лежит на вашем языке, а другая нет (здесь я игнорирую синтаксическую проблему и забываю о тот факт, что являются частью ввода). Дело в том, что свойство, которое вы здесь просматриваете, является механическим, а не семантическим (машины могут вычислять одну и ту же функцию, но другим способом).M , M x , nSM,Mx,n

Ariel
источник
Первый аргумент является формальным, но правильным. Второй аргумент сбивает меня с толку (я не уверен, что мог бы точно определить локальность / глобальность; и я не знаю, что значит вычислять функцию «из набора функций»).
Йирка Ханика
Первый аргумент действительно просто синтаксический, как упоминал Рафаэль в своем ответе. Локальная / глобальная проблема должна была показать разницу между рассуждением о результате на одном входе и всеми входами (я не имел в виду это в формальном смысле, это может означать что-то другое в другом контексте). Вычисление функции из заданного набора просто означает , что вы спрашиваете , будет ли функция вычисляется в . SMαS
Ариэль
Теорема Райса НЕ требует, чтобы один рассуждал о поведении машины на всех входах. Например, невозможно классифицировать программы на основании того, будут ли они в конечном итоге приниматься при запуске на входе «5». Или, скорее, вы можете определить такую ​​классификацию, которая просто отлично игнорирует поведение большинства входных данных, но классификация все еще не является рекурсивной.
Йирка Ханика
Это действительно сбивало с толку, поскольку можно определить как набор функций, которые выводят на некотором фиксированном входе. Спасибо, что подняли вопрос. 1S1
Ариэль
3

Теорема Райса говорит, что для любого нетривиального множества языков множество машин Тьюринга, которые распознают язык в  , неразрешимо. Википедия говорит, что конкретный язык является разрешимым. Так что нет никакого противоречия.LLL

Дэвид Ричерби
источник