Теорема об эквивалентности понятия вычислимой функции.
вычислима: ()
1) Если существует программа МНР, которая вычисляет эту функцию.
2) Если существует программа МТ-П, которая вычисляет эту функцию.
3) Если существует программа НАМ, которая вычисляет эту функцию.
Использование НАМ:
Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.
Пусть которая вычисляется на МТ-П, вычислим её на НАМ.
МТ-П:
НАМ:
Команда МТП: преобразуется по правилам:
Команда МТП: