Пятница, 24.11.2017, 14:15
ОТКРЫТАЯ ИНФОРМАТИКА
Приветствую Вас Гость | RSS
Главная Машина Поста Регистрация Вход
Меню сайта

Форма входа

Поиск

Календарь
«  Ноябрь 2017  »
ПнВтСрЧтПтСбВс
  12345
6789101112
13141516171819
20212223242526
27282930

Уроки 7-10

Машина Поста

Основные понятия: машина Поста

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

Эмиль Леон  Пост - американский математик и логик.  Один из основателей многозначной логики (1921);  трудился в области математической логики: создал алгебру Поста, классы Поста функций алгебры логики; предложил абстрактную вычислительную машину — машину Поста.

Структура машины Поста:

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (также как у машины Тьюринга). Каждая ячейка ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. 

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

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

Программа  состоит из конечного числа строк и использует всего 6 команд.


N. → J  - сдвиг вправо

N. ← J - сдвиг влево

N. 1 J - запись метки

N. 0 J  -удаление метки

N. ? J1, J0 - если в ячейке есть метка, то перейти к j1 строке программы, иначе перейти к j0 строке программы.

N. Stop - остановка

где N. — номер строки, J — строка на которую переходит управление далее.

Попытка стереть метку там, где ее нет, или поставить метку повторно считается ошибкой, и машина аварийно останавливается

Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки).

После запуска возможны варианты:

- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой Stop;

- работа никогда не закончится.

Все строки в программе нумеруются по порядку, это необходимо для работы команды ветвления (? n0,n1). С помощью этой команды можно также
строить циклы, как с предусловием, так и с постусловием.

Например, следующая программа перемещает каретку влево до первой отмеченной ячейки:
1. ←
2. ? 1,3
3. стоп

После команд "←”, "→”, "0” и "1” можно указать номер строки, на которую нужно перейти сразу после выполнения этой команды. Например, команда ← 3 означает "переместить каретку влево и перейти на строку 3”.

При работе с машиной Поста числа обычно записывают в унарной (единичной) системе счисления, в виде непрерывной цепочки меток нужной длины (вспомните счетные палочки в младшей школе).

Пример работы машины Поста: прибавление к числу единицы.


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


Вопросы:


1. Сравните машины Тьюринга и Поста.

2. Зачем нумеруются строки в программе для машины Поста?

Задачи:

1. Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.

2. Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.

3. Что делают следующие программы для машины Поста:
а) 1  1                 б) 1   ←                           в)  1      ? 2,3
    2  →                    2   ? 3,4                            2      1 4
    3  → 1                 3   1 1                               3      → 1
                              4   стоп                             4      стоп

Как будет работать каждая из программ при различных начальных состояниях ленты?

Компьютерный практикум:

(Методические материалы И.Г. Семакина)

1. На информационной ленте либо справа, либо слева от головки, стоящей под пустой клеткой, находится массив меток. Требуется присоединить к этому массиву одну метку. Составить универсальную программу. Реализуйте программу на учебной модели машины Поста. Протестируйте программу.

2. На ленте расположен массив из 2n-1 меток. Составить программу отыскания средней метки и стирания ее. Реализуйте программу на учебной модели машины Поста. Протестируйте программу.

3.  На ленте расположен массив из 2n меток. Составить программу, по которой машина раздвинет на расстояние в одну клетку две половины данного массива. Реализуйте программу на учебной модели машины Поста. Протестируйте программу.


Программное обеспечение:

Машина Поста программа (К.Поляков)


Дополнительные источники:

Материал "Машина Поста" (Планета Информатики)


Использованная литература:

1. К.Ю. Поляков, Е.А. Еремин "Элементы теории алгоритмов". Журнал "Информатика" №1, 2012 г.


Наш опрос
Сколько времени вы обычно проводите за комьпютером?
Всего ответов: 970

Друзья сайта
  • Министерство образования РБ
  • Официальный портал подготовки к ГИА и ЕГЭ
  • Всероссийская олимпиада школьников
  • Федеральный портал Российского образования
  • Институт развития образования РБ

  • Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0

    Copyright MyCorp © 2017 Бесплатный конструктор сайтов - uCoz