МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ
Суббота, 15.12.2018, 06:19
ГлавнаяРегистрацияВход Приветствую Вас Гость | RSS

Меню сайта

Категории раздела
Машина Тьюринга [4]
Машина Поста [2]
Практика [2]
Это интересно [1]
ЗАДАНИЕ 4 [1]

Наш опрос
Какой язык программирования Вы изучаете
Всего ответов: 954

Статистика

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

Форма входа


Главная » Файлы » УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА » Машина Поста

Эмулятор машины Поста
[ Скачать с сервера (173.8 Kb) ] 16.01.2013, 09:49

Эмулятор машины Поста

 Классическая машина Поста

Машина Поста - это универсальный исполнитель (абстрактная вычислительная машина), основанный на идеях работы американского математика Э.Л. Поста, целью которой было уточнение понятия алгоритма. Согласно тезису Поста, любой алгоритм может быть записан в виде программы для машины Поста.

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

Программа состоит из пронумерованных строк. В каждой строке записывается одна из следующих команд:

> N    переместить каретку вправо на 1 ячейку и перейти к строке с номером N

< N    переместить каретку влево на 1 ячейку и перейти к строке с номером N

0 N    записать в текущую ячейку «0» (стереть метку) и перейти к строке с номером N

1 N    записать в текущую ячейку «1» (поставить метку) и перейти к строке с номером N

? N, M      если текущая ячейка содержит «0» (не отмечена), то перейти к строке с номером N, иначе перейти к строке M

.         остановить программу

Номер строки перехода в командах >, <, 0 и 1 можно не указывать, при этом происходит переход к следующей строке.

Для завершения работы программы достаточно сделать переход на строку 0, например, так:

? 25, 0    остановить программу, если текущая ячейка содержит «1»  иначе перейти к строке 25

 

Троичная машина Поста

В троичной машине Поста используется расширенный алфавит, состоящий из трех символов: пробел, «0» и «1». Это позволяет программировать задачи, в которых числа записаны в двоичной системе счисления. Команды, отличающиеся от «стандартного» варианта машины Поста:

X N    записать в текущую ячейку пробел (стереть метку) и перейти к строке с номером N

0 N    записать в текущую ячейку «0» и перейти к строке с номером N

1 N    записать в текущую ячейку «1» и перейти к строке с номером N

Номер строки перехода может отсутствовать, при этом машина переходит на следующую строку программы.

Команда ветвления содержит три метки, разделенные запятыми:

? N,M,L    если текущая ячейка пустая, то перейти к строке с номером N, иначе если текущая ячейка содержит «0», то перейти к строке с номером M, иначе (если текущая ячейка содержит «1») перейти к строке L

 

Как работать с программой?

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

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее содержимое (в «классическом» варианте заменяется «0» на «1» или наоборот, в троичной машине Поста символы «пробел», «0» и «1» при последовательных двойных щелчках меняются циклически).

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

С помощью меню Алфавит можно переключать режим работы машины (двоичный или троичный алфавит). В классическом режиме меню Вид позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).

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

Четвертый столбец может содержать комментарий к каждой строчке программы. Добавить и удалить строки таблицы можно с помощью кнопок, расположенных слева от таблицы.

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.

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

Категория: Машина Поста | Добавил: i_elf
Просмотров: 4942 | Загрузок: 557 | Комментарии: 3 | Рейтинг: 5.0/1
Всего комментариев: 1
1 i_elf  
http://kpolyakov.narod.ru/ материал с сайта

Имя *:
Email *:
Код *:
Поиск

Друзья сайта
  • Творческий учитель
  • Сайт ООАКМР
  • Школьный сайт
  • Информатика учебник
  • МОИ

  • Copyright MyCorp © 2018 Сделать бесплатный сайт с uCoz