Теорема о рекурсии — различия между версиями
Строка 4: | Строка 4: | ||
|id=th1 | |id=th1 | ||
|about=О рекурсии | |about=О рекурсии | ||
− | |statement= Пусть <tex>U</tex> - [[Диагональный_метод|универсальная функция]], <tex>h</tex> - всюду определенная [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex> | + | |statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]], <tex>h</tex> {{---}} всюду определенная [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex> |
|proof= | |proof= | ||
Начнем с доказательства леммы. | Начнем с доказательства леммы. | ||
Строка 10: | Строка 10: | ||
|id=st1 | |id=st1 | ||
|statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\equiv</tex>. Тогда следущие два утверждения не могут быть выполнены одновременно: <br> | |statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\equiv</tex>. Тогда следущие два утверждения не могут быть выполнены одновременно: <br> | ||
− | * Пусть <tex>f</tex> - вычислимая функция. Тогда существует всюду определенное вычислимое <tex>\equiv</tex>-продолжение <tex>g</tex> функции <tex>f</tex>, т.е. такая <tex>g</tex> что <tex>D(g)=N</tex> и <tex>\forall x</tex> такого что <tex>f(x) \ne \perp</tex> выполнено <tex>f(x) \equiv g(x)</tex> | + | * Пусть <tex>f</tex> {{---}} вычислимая функция. Тогда существует всюду определенное вычислимое <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> функции <tex>f</tex>, т.е. такая <tex>g</tex> что <tex>D(g)=N</tex> и <tex>\forall x</tex> такого что <tex>f(x) \ne \perp</tex> выполнено <tex>f(x) \equiv g(x)</tex>. |
− | * Найдется такая всюду определенная вычислимая <tex>h</tex> что <tex>\forall n </tex> <tex>h(n) \not\equiv n</tex> | + | * Найдется такая всюду определенная вычислимая <tex>h</tex> что <tex>\forall n </tex> <tex>h(n) \not\equiv n</tex>. |
|proof= | |proof= | ||
От противного. Пусть оба утверждения выполнены. <br> | От противного. Пусть оба утверждения выполнены. <br> | ||
− | Определим функцию <tex>f</tex> так: <tex>f(x)=U(x,x)</tex>. Заметим что никакая всюду вычислимая функция не отличается от <tex>f</tex> всюду. <br> Согласно первому утверждению найдется всюду определенное вычислимое <tex>\equiv</tex>-продолжение <tex>g</tex> функции <tex>f</tex>. <br> Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x))</tex>, где <tex>h</tex> - функция из второго утверждения. <br >Если <tex>f(x) \ne \perp</tex>, то <tex>f(x)=g(x) \ne h(g(x))=t(x)</tex>, т.е. <tex>f(x) \ne t(x)</tex>. Если <tex>f(x)= \perp</tex>, то <tex>f(x) \ne t(x)</tex>, т.к. <tex>t</tex> - всюду определена. Значит <tex>f</tex> всюду отлична от <tex>t</tex>, противоречие. | + | Определим функцию <tex>f</tex> так: <tex>f(x)=U(x,x)</tex>. Заметим что никакая всюду вычислимая функция не отличается от <tex>f</tex> всюду. <br> Согласно первому утверждению найдется всюду определенное вычислимое <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> функции <tex>f</tex>. <br> Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x))</tex>, где <tex>h</tex> {{---}} функция из второго утверждения. <br >Если <tex>f(x) \ne \perp</tex>, то <tex>f(x)=g(x) \ne h(g(x))=t(x)</tex>, т.е. <tex>f(x) \ne t(x)</tex>. Если <tex>f(x)= \perp</tex>, то <tex>f(x) \ne t(x)</tex>, т.к. <tex>t</tex> {{---}} всюду определена. Значит <tex>f</tex> всюду отлична от <tex>t</tex>, противоречие. |
}} | }} | ||
− | Теперь определим отношение <tex>\equiv</tex> так: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex>. Покажем, что для него выполнено первое утверждение леммы. <br> Для заданной <tex>f</tex> определим <tex>V(n,x) = U(f(n), x)</tex>. <br> Так как <tex>U</tex> - универсальная функция, то найдется такая всюду определенная вычислимая <tex>s</tex>, что <tex>V(n,x) = U(s(n), x)</tex>. <br> Тогда <tex>\forall x, n </tex> <tex>U(f(n), x) = U(s(n), x)</tex>, значит <tex>\forall n </tex> <tex> s(n) \equiv f(n)</tex>, то есть <tex>s</tex> - всюду определенное <tex>\equiv</tex>-продолжение <tex>f</tex>. | + | Теперь определим отношение <tex>\equiv</tex> так: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex>. Покажем, что для него выполнено первое утверждение леммы. <br> Для заданной <tex>f</tex> определим <tex>V(n,x) = U(f(n), x)</tex>. <br> Так как <tex>U</tex> {{---}} универсальная функция, то найдется такая всюду определенная вычислимая <tex>s</tex>, что <tex>V(n,x) = U(s(n), x)</tex>. <br> Тогда <tex>\forall x, n </tex> <tex>U(f(n), x) = U(s(n), x)</tex>, значит <tex>\forall n </tex> <tex> s(n) \equiv f(n)</tex>, то есть <tex>s</tex> {{---}} всюду определенное <tex>\equiv</tex> {{---}} продолжение <tex>f</tex>. |
− | Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое что <tex>U_{h(n)} = U_n</tex> | + | Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое что <tex>U_{h(n)} = U_n</tex>. |
}} | }} | ||
Теорему о рекурсии можно переформулировать следущим образом. | Теорему о рекурсии можно переформулировать следущим образом. | ||
Строка 23: | Строка 23: | ||
|id=th2 | |id=th2 | ||
|about=О рекурсии | |about=О рекурсии | ||
− | |statement= Пусть <tex>V(n, x)</tex> - вычислимая функция.Тогда найдется такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex> | + | |statement= Пусть <tex>V(n, x)</tex> {{---}} вычислимая функция.Тогда найдется такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>. |
|proof= | |proof= | ||
− | Так как <tex>U</tex> - универсальная, то | + | Так как <tex>U</tex> {{---}} универсальная, то для любой вычислимой всюду определенной <tex>n</tex> найдется такая вычислимая всюду определенная <tex>num</tex>, что <tex>n=U_{num(n)}</tex>. Тогда найдется такая <tex>h</tex> что <tex>\forall n, x</tex> <tex>V(n, x) = U(h(num(n)), x)</tex>. <br >По доказанному найдется такое <tex>n_0</tex> что <tex>U_{n_0} = U_{h(n_0)}</tex>. <br> Возьмем <tex>p=U_{n_0}</tex>. Тогда <tex>V(p, x) = V(U_{n_0}, x) = U(h(num(U_{n_0})), x) = U(h(n_0), x) = U(n_0, x) = p(x)</tex>. |
}} | }} | ||
Неформально теорема о рекурсии утверждает то что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем. | Неформально теорема о рекурсии утверждает то что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем. | ||
==Пример использования== | ==Пример использования== | ||
− | Используя теорему о рекурсии приведем простое доказательство неразрешимости языка <tex>L=\{p|p(\epsilon)=\perp\}</tex> | + | Используя теорему о рекурсии приведем простое доказательство неразрешимости языка <tex>L=\{p|p(\epsilon)=\perp\}</tex>. |
{{Утверждение | {{Утверждение | ||
|id=st2 | |id=st2 | ||
Строка 36: | Строка 36: | ||
|proof= | |proof= | ||
Предположим обратное, тогда существует программа <tex>r</tex> разрещающая <tex>L</tex>. | Предположим обратное, тогда существует программа <tex>r</tex> разрещающая <tex>L</tex>. | ||
− | Рассмотрим следущую программу | + | Рассмотрим следущую программу: |
<code> | <code> | ||
p(x) | p(x) |
Версия 21:42, 20 января 2012
Теорема о рекурсии
Теорема (О рекурсии): | |||||
Пусть универсальная функция, — всюду определенная вычислимая функция. Тогда найдется такое , что — | |||||
Доказательство: | |||||
Начнем с доказательства леммы.
Теперь определим отношение | |||||
Теорему о рекурсии можно переформулировать следущим образом.
Теорема (О рекурсии): |
Пусть — вычислимая функция.Тогда найдется такая вычислимая , что . |
Доказательство: |
Так как По доказанному найдется такое что . Возьмем . Тогда . | — универсальная, то для любой вычислимой всюду определенной найдется такая вычислимая всюду определенная , что . Тогда найдется такая что .
Неформально теорема о рекурсии утверждает то что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
Пример использования
Используя теорему о рекурсии приведем простое доказательство неразрешимости языка
.Утверждение: |
Язык неразрешим. |
Предположим обратное, тогда существует программа p(x) if r(p) return 1 while true Пусть . Тогда условие выполняется и . Противоречие. Если , то не выполняется и . Противоречие. |
Источники
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999