теорема Райса

[Михаиль]

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

вопрос- где можно почитать об этом побольше

это теория алгоритмов, рекурсивные и частично рекурсивные функции

[Профессор Снэйп]

Прочитать об этом можно в книге Х. Роджерса "Теория рекурсивных функций и эффективная вычислимость", а также во многих других учебниках по теории вычислимости.

P. S. В электронном виде "Роджерс" вроде бы где-то есть, хотя я не видел. Поищите. Если найдёте, киньте ссылку. Его у меня многие спрашивают (хотя у самого есть бумажная версия, так что лично для меня не сильно актуально).

Ещё можете сходить сюда Это то, что я читаю первокурсникам в НГУ. Терема Райса является простым следствием теоремы о неподвижной точке (которая фигурирует в тексте как следствие 5 на стр. 99). Я обычно даю её (теорему Райса) на семинарах в качестве простого упражнения (ну и на экзамене как вопрос на тройку )

Надеюсь, модераторы не воспримут ссылку как неуместную рекламу.

[Михаиль]

спасибо..почитаю,хотя экзамен уже прошел

с удивлением увидел вопрос яляется ли объединение двух регулярных языков объязательно регулярным языком и ответил нет, хоть вроде и знал что оно закрыто насчет операции

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

[Профессор Снэйп]

Михаиль писал(а):

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

Ну что же Вы так Замкнутость относительно объединения --- это прямое следствия определения множества регулярных языков.

Михаиль писал(а):

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

Вот ещё продолжение для старшекурсников. Наслаждайтесь

Правда, оно пока не дописано. В будущем добавлю туда ещё несколько глав. В частности, главы, посвящённые аналитической и гиперарифметической иерархиям, а также доказательства нескольких классических теорем (теорема о том, что порядок $\omega_1^{CK} \times (1 + \eta)$ конструктивизируем и теорема Лахлана о том, что решётки вычислимо перечислимых надмножеств гипергиперпростых множеств по модулю конечных множеств --- это в точности счётные булевы алгебры, имеющие $\Sigma^0_3$-представление).

[Михаиль]

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

про язык я знал а вот что означал имено регулярный язык забыл

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

и любое ли рекурсивное множество является множесто определения какой то рекурсивной функции ответ да т.к. ввиде любой функции можно взять хараткеристическую функцию множества

я в правильном ключе рассуждаю или нет?

[Профессор Снэйп]

Михаиль писал(а):

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

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

Нет, оно не является рекурсивно перечислимым. Зато дополнение к нему рекурсивно перечислимо и более того, креативно. Дополнение --- это в точности множество $K_2$ из предложения 16 на стр. 108-109 в так понравившемся Вам конспекте

Михаиль писал(а):

и любое ли рекурсивное множество является множесто определения какой то рекурсивной функции ответ да т.к. ввиде любой функции можно взять хараткеристическую функцию множества

я в правильном ключе рассуждаю или нет?

Частично рекурсивной функции, Вы хотите сказать. Ибо рекурсивная функция всюду определена

Каждое рекурсивное множество по теореме Поста является рекурсивно перечислимым и, значит, по теореме о характеризации рекурсивно перечислимых множеств является областью определения некоторой частично рекурсивной функции. Отсылаю Вас к стр. 101-103 того же конспекта.

P. S. Сходите, что ли, на www.gramota.ru или какой-нибудь другой подобный сайт и подтяните свой русский язык. У Вас с орфографией большие проблемы, невозможно нормально воспринимать Ваши сообщения.

[Михаиль]

Спасибо
сейчас буду читать..
т.к. понял, что экзамен значит я не сдал.

с грамматикой подтянусь

[e2e4]

А не могли бы Вы на пальцах объяснить, что означает формулировка

Цитата:

свойсива рекурсивной функции можно распознать, смотря на программу лишь в двух случаях - это свойство присуще любой функции или это свойство присуще ни одной функции...

?
Если честно, ничего не понял.
Какое это может иметь значение для практики программирования?

P.S. Что такое рекурсия, знаю, применял на практике неоднократно.

[Профессор Снэйп]

e2e4 писал(а):

А не могли бы Вы на пальцах объяснить, что означает формулировка

Цитата:

свойсива рекурсивной функции можно распознать, смотря на программу лишь в двух случаях - это свойство присуще любой функции или это свойство присуще ни одной функции...

?
Если честно, ничего не понял.
Какое это может иметь значение для практики программирования?

P.S. Что такое рекурсия, знаю, применял на практике неоднократно.

А на практике программирования это никто и не применяет Речь идёт об абстрактной вычислимости

Она имеет отношение к практическому программированию примерно такое же, как специальная теория относительности к самолётостроению. Представьте картину: конструкторы маются, придумывают нетривиальные решения и строят самолёты которые летают в 5, в 10 и даже в 15 раз быстрее скорости звука. А тут приходит студент физик и говорит: да сколько не майтесь, всё равно быстрее скорости света не полетит! Он прав? Безусловно! Только практической ценности в его замечании --- нуль.

А что касается теоремы Райса... Ну вот берём мы такое свойство программ (синтаксически правильно написанных): при любых входных данных заканчивать вычисления за конечное число шагов, не впадая в бесконечный цикл. Теорема Райса гарантирует, что не существует другой программы, которая бы по тексту исходной программы распознавала, обладает она или нет этим свойством. Но поскольку речь идёт просто о конечном числе шагов вычисления, которое никак не ограничивается сверху, то с практической точки зрения отсутствие такой программы мало что значит.

[PAV]

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

Так что с практической точки зрения важно знать, что в принципе возможно сделать, а что - никак нельзя.

[Профессор Снэйп]

PAV писал(а):

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

Так что с практической точки зрения важно знать, что в принципе возможно сделать, а что - никак нельзя.

Только "алгоритмически неразрешима", а не "алгебраически" "Проблема остановки" действительно неразрешима, она задаётся креативным множеством. Да, это классический факт. В качестве другого примера можно привести решённую Матиясевичем десятую проблему Гильберта: не существует алгоритма, который бы за конечное число шагов, получив на вход многочлен с целыми коэффициентами (от нескольких переменных), определял, есть ли у него целочисленные корни.

Другое дело, что разрешимость "за конечное число шагов" и "разрешимость за приемлемое время" --- совершенно разные вещи. На практике полиномиально неразрешимые проблемы вызывают гораздо больший интерес, чем алгоритмически неразрешимые. Впрочем, у любой абстрактной, оторванной от практики теории всегда найдётся множество поклонников, которым она интересна за свою, допустим, внутреннюю красоту. И на практику этим адептам глубоко положить. Несмотря на то, что подавая заявки на гранты, они без устали твердят о практическом приложении своих исследований Ну а как иначе? Гранитом науки сыт не будешь

[e2e4]

Спасибо за разъяснение!

Профессор Снэйп писал(а):

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

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

[Профессор Снэйп]

e2e4 писал(а):

Профессор Снэйп писал(а):

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

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

Да, естественно. Это подразумевалось. Хотя... в данном случае это не обязательно Внимательно вчитайтесь во фразу "при любых входных данных".

Вот, допустим, программа $P$ вычисляет функцию $f_P(x)$. (как обычно, функция считается определённой в тех и только в тех точках, в которых программа не зацикливается, а за конечное число шагов выдаёт ответ). Имеем две проблемы:

1) По данным $P$ и $x$ выяснить, верно ли, что $f_P(x)$ определено.

2) По данному $P$ выяснить, верно ли, что $\forall x (f_P(x)$ определено $)$.

Первая задача --- это "проблема остановки". Она не разрешима, но перечислима (то есть мы можем перечислять пары $\langle P, x \rangle$, для которых она решается положительно тем способом, который Вы указали.

Вторая задача сложнее, она даже не перечислима. Можно показать, что если мы заведём "оракул" для проблемы остановки (то есть некий чёрный ящик, "мистическое" устройство, которое непонятно как работает, но которое, получив на входе пару $\langle P, x \rangle$, за конечное время решает для неё первую задачу) и прицепим его к вычислительному устройству, то для этой, более сложной машины, первая задача станет разрешимой, а вторая... будет эквивалентна проблеме остановки машины с оракулом

[e2e4]

Вы совершенно правы, уже после того как я написал ответ, тоже подумал об условии "при любых входных данных".
Однако, в реальных программах (в отличие от абстрактных алгоритмов), всегда имеется некоторое конечное минимальное $\epsilon$-приращение перемнной, при котором она изменяет свое внутреннее представление в памяти (квантование из-за конечного кол-ва битов, представляющих значение переменной). Таким образом, все возможные входные данные - перечислимы.

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

Другое дело, если функция рекурсивная, и вызывает сама себя с пременным кол-вом параметров... особенно, если эти параметры - случайные числа... тут надо подумать, перечислимы ли все исходы...

Добавлено спустя 2 минуты 39 секунд:

Склоняюсь, что все-таки, перечислимы.

[Профессор Снэйп]

e2e4 писал(а):

Но все-равно, на реальной вычислительной машине имеется конечно кол-во ячеек памяти, спасобных хранить все конечные данные.

Реальная вычислительная машина --- это конечный автомат Со всеми вытекающими...

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