|
1. Машина Тьюринга
Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью «О вычислимых числах в приложении к проблеме разрешения», которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов.
Предыстория создания этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача до-казательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как «проблему разрешимости» - нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.
Статья Тьюринга как раз и давала ответ на эту проблему - вторая про-блема Гильберта оказалась неразрешимой. Но значение статьи Тьюринга выходило далеко за рамки той задачи, по поводу которой она была написана.
Приведем характеристику этой работы, принадлежащую Джону Хоп-крофту: «Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга».
Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу.
.
Пpогpамма для машины Тьюpинга состоит из последовательности инстpукций. Каждая инстpукция имеет вид
CurrentState CurrentSymbol NextSymbol NextState Move
где
CurrentState - текущее внутpеннее состояние,
CurrentSymbol - обозpеваемый символ,
NextSymbol - символ, котоpый пишется в обозpеваемую ячейку,
NextState - последующее внутpеннее состояние.
Move - напpавление сдвига головки ('L' или 'R' ), 'L' означает сдвиг головки влево, 'R' - сдвиг головки впpаво на одну ячейку.
Пpедполагается, что в обе стоpоны от введенной последовательности символов находится бесконечное количество символов пpобел (пробел будем обозначать символом "b").
Hачальное внутpеннее состояние - "A", конечное внутреннее состояние - "Z".
Работа ма
|
На уровень вверх
Купить