Неотделимые множества — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: g(n) \neq \bot </tex>.
 
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: g(n) \neq \bot </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>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.
  
 
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.
 
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.
 +
}}
 +
 +
{{Лемма
 +
|statement=
 +
Существует вычислимая функция, значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.
 +
|proof=
 +
Рассмотрим функцию
 +
<tex>f(n) = \begin{cases}
 +
  0 & \text{, }U(n, n) \neq 0 \text{ и }U(n, n) \neq \bot \\
 +
  1 & \text{, }U(n, n) = 0 \\
 +
  \bot & \text{, }U(n, n) = \bot
 +
\end{cases}</tex>
 +
 +
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>.
 +
 +
<tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>.
 +
 +
<tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Но тогда по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.
 
}}
 
}}

Версия 00:47, 1 декабря 2010

Лемма:
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.
Доказательство:
[math]\triangleright[/math]

Рассмотрим функцию [math]f(n) = U(n, n) + 1[/math], где [math]U(n, n)[/math]универсальная функция.

Предположим, у нее существует всюду определенное продолжение [math]g(n)[/math]. Это значит, что [math]f(n) \neq \bot \Rightarrow g(n) = f(n)[/math] и [math]\forall n: g(n) \neq \bot [/math].

По определению универсальной функции [math]g(n) = U(i, n)[/math] для некоторого [math]i[/math]. Тогда [math]g(i) = U(i, i)[/math]. Поскольку [math]g(n)[/math] всюду определена, то [math]U(i, i) \neq \bot[/math]. Значит, [math]g(i) = f(i) = U(i, i) + 1[/math]. Получили противоречие.

Таким образом, построенная функция [math]f(n)[/math] не имеет всюду определенного вычислимого продолжения.
[math]\triangleleft[/math]
Лемма:
Существует вычислимая функция, значения которой принадлежат множеству [math]\{0, 1, \bot\}[/math], не имеющая всюду определенного вычислимого продолжения.
Доказательство:
[math]\triangleright[/math]

Рассмотрим функцию [math]f(n) = \begin{cases} 0 & \text{, }U(n, n) \neq 0 \text{ и }U(n, n) \neq \bot \\ 1 & \text{, }U(n, n) = 0 \\ \bot & \text{, }U(n, n) = \bot \end{cases}[/math]

Предположим, у нее существует всюду определенное продолжение [math]g(n)[/math].

[math]g(n) = U(i, n)[/math] для некоторого [math]i[/math].

[math]g(i) = U(i, i)[/math]. Поскольку [math]g(n)[/math] всюду определена, то [math]U(i, i) \neq \bot[/math]. Но тогда по построению функции [math]f(n)[/math] видим, что [math]f(i) \neq U(i, i)[/math]. Получили противоречие.
[math]\triangleleft[/math]