Типы алгоритмов. История создания

Основные АМ

• Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г.
• Машина Поста (МР) предложена Постом в 1937 г.
• Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.

• Машина Тьюринга

• -абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
• Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.