Озадачен теоремой Райс

Реферат: Согласно теореме Райс, все невозможно. И все же, я делаю это якобы невозможное постоянно!

Конечно, теорема Райс не просто говорит, что «все невозможно». В нем говорится что-то более конкретное: «Каждое свойство компьютерной программы не вычислимо».

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

Это то, что говорит или, кажется, говорит теорема. И, вероятно, множество очень умных людей тщательно проверили правильность этой теоремы. Но, похоже, это совершенно не поддается логике! Есть множество свойств программ, которые тривиально вычислить! Например:

• Сколько шагов выполняет программа перед остановкой? Решить, является ли это число конечным или бесконечным, - это как раз проблема Халтинга, которая не вычислима. Решить, является ли это число большим или меньшим некоторого конечного , тривиально! Просто запустите программу до шагов и посмотрите, останавливается она или нет. Легко!$n$$n$

• Точно так же, использует ли программа больше или меньше единиц памяти на своих первых шагах выполнения? Тривиально вычислимо.$n$$m$

• Упоминает ли текст программы переменную с именем ? Тривиальный текстовый анализ покажет ответ.$k$

• Программа вызывает команду ? Снова отсканируйте текст программы в поисках имени этой команды.$\sigma$

Я вижу множество свойств, которые также выглядят не вычисляемыми; Например, сколько дополнений выполняет полный прогон программы? Ну, это почти то же самое, что спрашивать, сколько шагов выполняет программа, что фактически является проблемой остановки. Но, похоже, существует множество программных свойств, которые очень легко вычислить. И все же теорема Райс настаивает на том, что ни одна из них не является вычислимой.

Что мне здесь не хватает?

Для целей этого обсуждения «программа» - это фрагмент кода, который всегда принимает целое число в качестве входных данных и либо выполняется вечно, либо возвращает целое число. Мы говорим , что две программы и г являются экстенсионально равны , если они вычислить ту же функцию, то есть для каждого числа п либо как е ( п ) и г ( п ) бежать навсегда, или они оба прекратить и выводить тот же номер.$f$$g$$n$$f(n)$$g(n)$

Экстенсиональное свойство программ является свойство , что уважает экстенсиональное равенство, то есть, если е и г является экстенсионально равно , то они либо оба имеют свойство P или оба не имеют его.$P$$f$$g$$P$

Вот некоторые примеры , не являющиеся -extensional свойств:

1. Программа останавливается в течение шагов. (Мы всегда можем изменить программу на равную по длине и работать дольше.)$n$
2. Программа использует меньше чем ячеек памяти в течение первых m шагов выполнения. (Мы всегда можем изменить программу до экстенсивно равной, чтобы она использовала некоторую память без веской причины.)$n$$m$
3. В тексте программы упоминается переменная с именем k. (Мы можем переименовать переменные.)
4. $\sigma$$\sigma$$\sigma$

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

Теорема (Райс): вычислимое экстенсиональное свойство программ либо содержит все программы, либо их нет.

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

Фундаментальное недоразумение:

Каждое свойство компьютерной программы не вычислимо

$\emptyset \subset P \subset \mathsf{RE}$

$\qquad \displaystyle \{ \langle M \rangle \mid f_M \in P \}$

$P$

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

Похоже, мало что известно о синтаксических свойствах; см этот вопрос .