Эквивалентность трех подходов к понятию алгоритм.

1.2.1  Теорема об эквивалентности понятия вычислимой функции.

  вычислима: ()

1) Если существует программа МНР, которая вычисляет эту функцию.

2)                       Если существует программа МТ-П, которая вычисляет эту функцию.

3)                       Если существует программа НАМ, которая вычисляет эту функцию.

Использование НАМ:          

Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

 Пусть  которая вычисляется на МТ-П, вычислим её на НАМ.

МТ-П:  

НАМ:  

Команда МТП:  преобразуется по правилам:

Команда МТП: