Неотделимые множества — различия между версиями
| Строка 3: | Строка 3: | ||
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения. | Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения. | ||
|proof= | |proof= | ||
| − | Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> - [[Диагональный метод.|универсальная функция]]. Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>\forall n: g(n) \neq \bot </tex> и <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> | + | Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> {{---}} [[Диагональный метод.|универсальная функция]]. Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>\forall n: g(n) \neq \bot </tex> и <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex>. По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>f(i) = U(i, i) \neq \bot</tex>. Значит, <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие. Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения. |
}} | }} | ||
Версия 20:35, 30 ноября 2010
| Лемма: |
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения. |
| Доказательство: |
| Рассмотрим функцию , где — универсальная функция. Предположим, у нее существует всюду определенное продолжение . Это значит, что и . По определению универсальной функции для некоторого . Тогда . Поскольку всюду определена, то . Значит, . Получили противоречие. Таким образом, построенная функция не имеет всюду определенного вычислимого продолжения. |
