Разрешимые (рекурсивные) языки

Определение:

Язык [math]L[/math] называется разрешимым (рекурсивным), если существует такая программа [math] p [/math], что [math] \forall w \in L: p(w) = 1[/math], а для [math] \forall w \notin L: p(w) = 0[/math].

Примеры

Пример разрешимого множества

Утверждение:

Язык чётных чисел разрешим.

[math]\triangleright[/math]

Приведём программу, разрешающую наш язык: [math]p(i)[/math] if (остаток от деления i на 2 = 0) return 1 else return 0 Заметим, что программа нигде не может зависнуть.

[math]\triangleleft[/math]

Пример неразрешимого множества

Определение:

Язык [math] U = \{\langle p, x \rangle \ |\ p(x) = 1\} [/math] называется универсальным.

Утверждение:

Универсальный язык неразрешим.

[math]\triangleright[/math]

Докажем от противного. </br> Пусть язык [math] U [/math] разрешим. </br> Тогда существует такая программа [math] u [/math], что [math]p(i)[/math] if (остаток от деления i на 2 = 0) return 1 else return 0 Программа нигде не может зависнуть и таким образом разрешает наш язык.

[math]\triangleleft[/math]