Основные теоремы теории алгоритмов.

Теорема 1:Функцияfвычислима тогда и только тогда, когда перечислим ее график, то есть множество всех пар вида <x,f(x)>.

Теорема 2:Подмножество А перечислимого множества Х разрешимо относительно Х тогда и только тогда, когда А и Х\А перечислимы.

Теорема 3:Если А и В перечислимы, то АВ и АВ также перечислимы.

Теорема 4:В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением (в силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

Теорема 5: Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х.