<<
>>

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

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

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

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

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

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

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

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

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

МТ-П:

НАМ:

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

Команда МТП:

<< | >>
Источник: Конспекты лекций по математической логике. 2017

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

  1. 1.1. Концептуальные основы формирования моделей экономического поведения предпринимательских структур
  2. СООТНОШЕНИЕ ЭВРИСТИЧЕСКОЙ И РЕГУЛЯТИВНОЙ ФУНКЦИИ ФИЛОСОФСКИХ ПРИНЦИПОВ в ФОРМИРОВАНИИ НОВОЙ ФИЗИЧЕСКОЙ ТЕОРИИ
  3.   2.1.7. Физика, математика и компьютерные науки  
  4. Список сокращений
  5. ТИПОЛОГИЧЕСКИЙ ПОДХОД
  6. 2.2. Внешние свойства уголовного наказания
  7. Общие подходы к управлению различными видами активов в условиях инфляции
  8. 2.4. Основные параметры денежных потоков
  9. 2. Форма стоимости, или меновая стоимость
  10. Знание как сознательный феномен Катречко С.Л.
  11. 2. Конечноразностные методы
  12. 4. Проекционные методыОбширный класс методов приближенного решения уравнений вида Аи = / использует следующий ПОДХОД: решение ищется В виде UN = = где коэффициенты а, определяются из условия равенства
  13. Психодиагностические методики, виды методик.
  14. 1.2 Эквивалентность трех подходов к понятию алгоритм.