Машина Поста

ля, учащихся друг с другом).

Изучение нового материала

Учитель:
Тема урока: "Автоматическая обработка информации".
Открываем тетради, записываем число, тему урока

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

Ал - горитм, по которому работает машина Поста, будем на - зывать программой.
Под словом "программа" понимают алгоритм, записанный по строгим правилам языка команд исполнителя - на языке программирования для данного исполнителя.


Назначение машины Поста - производить преобразования на информационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты - результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.