Алан Тьюринг

В 1936 году американский математик Алан Тьюринг в статье "О вычислительных числах" и, независимо от него, американский математик и логик Э.Пост (уроженец Польши) выдвинули и разработали концепцию абстракт-ной вычислительной машины. "Машина Тьюринга" - гипотетический универсальный преобразователь дискретной информации, теоретическая вычислительная система.

Тьюринг и Пост показали принципиальную возможность решения автоматами любой проблемы при условии возможности ее алгоритмизации с учетом выполняемых ими операций. Этими работами теоретически была доказана возможность создания универсальной цифровой вычислительной машины.

Тьюринг ввел математическое понятие абстрактного эквивалента вычислительного алгоритма, получившего название машины Тьюринга.

Машина Тьюринга состоит из контрольного модуля, читающей и пишущей головки (устройства ввода/вывода) и бесконечной ленты, разделенной на клетки. Поведение машины определяется конечным набором формул перехода типа ввод-вывод-сдвиг. Формула перехода включает пять символов, например: AT - T A, это означает, что если контрольный модуль находится в состоянии А и головка сканирует на ленте символ Т, то головка сначала запишет символ Т, затем сдвинется на одну клетку влево, на одну клетку вправо или останется на месте,в зависимости от значения (-, +, или 0 соответственно), перейдет в новое состояние.

XX век