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

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

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

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

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

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

 

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

        

 

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

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

МТ-П:  

НАМ:  

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

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

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

 

Логика - доступно для всех