Презентация к лекции: Машина Поста

Автоматическая обработка информации.

Машина Поста

Автома

«Сами машины - это пустые перчатки,  Но их надевает человеческая рука,  Которая может быть хорошей или плохой»

Р. Брэдбери.

План

1. Теория Алгоритмов

2. Машина Поста

1.Теория Алгоритмов

В 30-х годах XX века возникает новая наука — теория алгоритмов.

Общая теория алгоритмов занимается проблемой эффективной вычислимости.

Разработано несколько формальных определений алгоритма, в которых эффективность и конечность вычислений могут быть определены количественно – числом элементарных шагов и объемом требуемой памяти.

Теория Алгоритмов

Подобными моделями алгоритмических преобразований символьной информации являются:

• рекурсивные функции;
• машина Тьюринга;
• машина Поста;
• конечные автоматы;
• ассоциативное исчисление или нормальные алгоритмы Маркова.

Теория Алгоритмов

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

• Алгоритмические машины (АМ).
• Функции вычислимые алгоритмом.
• Исчисления.

Алгоритмические машины (АМ).

имеют единственный процессор, выполняющий небольшой набор очень примитивных действий,

простую структуру данных (структуру памяти) в виде бесконечной ленты,

простую логику (правила) управления процессором.

Основные АМ

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

Функции вычислимые алгоритмом

• алгоритм не определяется формально, а существует как бы в виде «всем понятной механической процедуры».
• любая функция, вычислимая на интуитивном (содержательном) уровне, должна быть сконструирована из базовых

• Рекурсивные функции на множестве натуральных чисел были предложены Клини в 1938 г.

• Конструктивные механизмы рекурсивных функций очень просты, их применение в процессе построения «функции от функции» позволяет явно выстраивать структуру функции в отличие от АМ, где функция определяется процедурно, через последовательность действий.

Исчисления.

• Исчисление функций , вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г.
•  -исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г.
• Формальные грамматики , порождающие языки, предложены Хомским в 1953 – 1956 г.

Теория Алгоритмов

Вопрос, на который ищет ответ теория алгоритмов: для всякой ли задачи обработки информации может быть построен алгоритм решения ?

Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

МАШИНА ТЬЮРИНГА

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

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

Каретка

Бесконечная лента

Программа

МАШИНА ПОСТА

Практически одновременно с Тьюрингом (1936-1937 гг.) другую модель алгорит- мической машины описал Эмиль Пост . Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным слу­чаем машины Тьюринга.

2.Машина Поста

Бесконечная лента

Каретка

Программа

Машина Поста

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

Под словом « программа » мы всегда будем понимать алгоритм , записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.

Опишем архитектуру машины Поста. Име­ется бесконечная информационная лента, разделенная на позиции — клетки. В каждой клетке может либо сто­ять метка (некоторый знак), либо отсутствовать (пусто).

v

v

v

v

v

Вдоль ленты движется каретка — считывающее устройство. На рисун­ке она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево . Клетку, под которой установлена каретка, будем называть текущей .

Каретка является еще и процессором машины. С ее помощью машина может:

• распознать, пустая клетка или помеченная знаком;

• стереть знак в текущей клетке;

• записать знак в пустую текущую клетку.

Машина Поста

Существенное отличие каретки-процессора машины Поста от процессора компьютера состоит в том, что в компьютере возможен доступ процессора к ячейкам памяти в произвольном порядке , а в машине Поста — только последовательно.

Система команд машины Поста

Команда

Действие

n ← m

Сдвиг каретки на шаг влево и переход к выполнению команды с номером m

n → m

Сдвиг каретки на шаг вправо и переход к выполнению команды с номером m

n v m

n ↕ m

Запись метки в текущую пустую клетку и переход к выполнению команды с номером m

n !

Стирание метки в текущей клетке и переход к выполнению команды с номером m

n ? m,k

Остановка выполнения программы

Переход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номером m, если непустая – команда с номером k

Машина Поста

Назначение машины Поста — производить преобразования на инфор­мационной ленте.

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

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

v

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Пример программы решения задачи на машине Поста

Пример программы решения задачи на машине Поста

Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Машина Поста

v

v

v

v

v

Команда

1 ↕ 2

Действие

2 → 3

Стирание метки; переход к следующей команде

Сдвиг вправо на один шаг

3 ? 2,4

4 ← 5

Если клетка пустая, то переход к команде 2, иначе – к команде 4

5 v 6

Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)

6 !

Запись метки в пустую клетку

Остановка машины

Машина Поста

В процессе выполнения приведенной программы многократно повторя­ется выполнение команд с номерами 2 и 3 . Такая ситуация называется циклом .

Напомним, что цикл относится к числу основных алгоритмичес­ких структур вместе со следованием и ветвлением.

Задание 1

Машина Поста

На информационной ленте машины Поста расположен массив из N меток. Каретка расположена под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?

1 → 2

Назначение машины Поста — производить преобразования на инфор­мационной ленте.

2 ↕ 3

3 → 4

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

4? 5, 2

5 ← 6

6 V 7

7 !

Задание 2

Машина Поста

На ленте поставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.

Назначение машины Поста — производить преобразования на инфор­мационной ленте.

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

Задание 3

Машина Поста

Составить программу для прохождения каретки от левой метки к правой. Количество пустых клеток между метками неизвестно.

• Начальное состояние :

• Конечное состояние:

Назначение машины Поста — производить преобразования на инфор­мационной ленте.

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

…

۷

۷

…

…

۷

۷

…

Задание 4

Машина Поста

Составить программу перевода информационной ленты из начального состояния в конечное:

• Начальное состояние:

• Конечное состояние:

Назначение машины Поста — производить преобразования на инфор­мационной ленте.

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

…

۷

۷

۷

۷

۷

۷

…

…

۷

۷

۷

۷

۷

۷

۷

…

Домашнее задание:

Подготовьте сообщение:

• «Какие бывают машины Тьюринга?»
• «Эзотерические языки программирования»
• «Рекурсивные функции»