Одно из утверждений о теореме Райса приведено на странице 35 «Вычислительная сложность: современный подход» (Арора-Барак):
Частичная функция от до - это функция, которая не обязательно определяется на всех ее входах. Мы говорим, что TM вычисляет частичную функцию если для каждого для которого определено , и для каждого для которого не определено, попадает в бесконечный цикл при выполнении на входе . Если - это набор частичных функций, мы определяем как булеву функцию, которая на входах выводит 1 тогда и только тогда, когда { 0 , 1 } ∗ M f x f M ( x ) = f ( x ) x f M x S f S α M αвычисляет частичную функцию в . Теорема Райса говорит, что для любого нетривиального функция не вычислима.f S
Википедия утверждает, что языки машин ограниченного времени ТУЗЫ полны. Я ожидаю, что этот язык выглядит примерно так: принимает менее чем за шагов . Итак, пусть это некоторый DTM, который решает этот ограниченный язык за экспоненциальное время. Кажется, что этот DTM решает какое-то свойство для ВСЕХ машин Тьюринга, поэтому моя интуиция говорит мне, что теорема Райс исключает такое решение. Но, очевидно, вычисляет общую функцию. x n } M M
Чего мне не хватает в связи между этим языком и теоремой Райс?
Теорема Райса говорит, что вы ничего не можете сказать об окончательном поведении программы, когда ее оставляют запускать до бесконечности - независимо от того, как вы классифицируете программы, будут две программы, которые будут сходиться к одному и тому же конечному поведению (вычисляемая функция ) хотя вы их классифицировали по разному.
Но важно, чтобы программы запускались до бесконечности. Чтобы выяснить, что они делают на первых шагах, вы можете просто смоделировать их на первых шагах, а затем прекратить давать свой вердикт о том, как ведет себя программа. Подобное моделирование до бесконечности не работает, потому что если симулируемая программа никогда не заканчивается на симулированном входе, ваш классификатор также будет расходиться вместо предоставления классификации.нn n
источник
Во-первых, слова на вашем языке не являются кодировками машин, они содержат больше информации, поэтому вы не можете напрямую применять теорему Райса. Тем не менее, теорема Райса говорит о невозможности рассуждения о функции, вычисляемой машиной Тьюринга (а именно, лежит ли она в некотором множестве ). Это не тот случай, поскольку, как упоминал Рафаэль, существуют две машины которые вычисляют одну и ту же функцию, но одна лежит на вашем языке, а другая нет (здесь я игнорирую синтаксическую проблему и забываю о тот факт, что являются частью ввода). Дело в том, что свойство, которое вы здесь просматриваете, является механическим, а не семантическим (машины могут вычислять одну и ту же функцию, но другим способом).M , M ′ x , nS M,M′ x,n
источник
Теорема Райса говорит, что для любого нетривиального множества языков множество машин Тьюринга, которые распознают язык в , неразрешимо. Википедия говорит, что конкретный язык является разрешимым. Так что нет никакого противоречия.LL L
источник