Краткий ответ: перед нами параграф учебника (Босова, информатика) про машину Поста — пример автоматического исполнителя обработки информации. Ниже — его связный пересказ с восстановленными ключевыми определениями, чтобы понятен был принцип.
Что такое машина Поста
Это абстрактный исполнитель для обработки информации. Алгоритм, записанный по строгим правилам языка команд этого исполнителя, называется программой (программа — всегда запись по правилам языка исполнителя).
Устройство (архитектура)
- Информационная лента — бесконечная, разбита на клетки. В каждой клетке либо стоит метка (знак), либо пусто.
- Каретка — считывающее устройство, обозначается стрелкой. Она может смещаться на одну клетку влево или вправо. Клетка под кареткой — текущая.
- Каретка одновременно является процессором и умеет:
- распознать, пустая клетка или помеченная;
- стереть знак в текущей клетке;
- записать знак в пустую текущую клетку.
Если метки заменить на 1, а пустые клетки — на 0, лента становится аналогом двоичного кода сообщения. Отличие от компьютера: процессор ЭВМ обращается к памяти в произвольном порядке, а каретка — только последовательно (шаг за шагом).
Исходное состояние ленты — это исходные данные задачи, конечное — результат. В исходные данные входит и начальное положение каретки.
Система команд
Запись команды: \(\;n.\ \text{операция}\ ;\ m\;\), где \(n\) — номер команды в программе, \(m\) — номер следующей команды. Основные операции: стереть метку, записать метку, сдвиг вправо, сдвиг влево, остановка. Есть условный переход: в зависимости от содержимого текущей клетки выполняется команда с номером \(m\) (одно значение) или с другим номером. Исполнение идёт с команды №1 до команды «остановка».
Пример и цикл
В примере программа должна стереть знак в текущей клетке и присоединить его слева к группе знаков справа. Команды 2 и 3 (сдвиг вправо, проверка клетки, сдвиг влево) многократно повторяются — это цикл. Цикл — одна из основных алгоритмических структур наряду со следованием и ветвлением.
Игра Баше
Правила: 21 (или 16, 11 …) фишка, игроки берут по очереди от 1 до 4 фишек, проигрывает взявший последнюю. Выигрышная тактика у второго игрока: брать столько фишек, чтобы сумма с ходом соперника (за предыдущий ход) была равна 5.
Машина играет второй, метки на ленте — фишки; человек стирает метки первым. Стирать можно только подряд. Программа (таблица 2.3) в цикле: машина ждёт появления пустой клетки (ход человека), выводит каретку на 5-ю (10-ю, 15-ю…) позицию — там при любом ходе соперника стоит метка, стирает её, шагает влево и возвращается к первой помеченной клетке, затем снова ждёт хода человека. Выигрыш: перед ходом человека остаётся одна метка.
Условие безошибочной игры
Машина всегда выигрывает, если начальное число меток имеет вид \[ N = 5n + 1, \] где \(n\) — натуральное число (то есть 1, 6, 11, 16, 21 …). Иначе машина может проиграть.
Итог: когда возможна автоматическая обработка информации
- информация представлена в формализованном виде — в конечном алфавите знаковой системы;
- есть исполнитель с конечной системой команд, достаточной для алгоритмов нужного класса задач;
- реализовано программное управление работой исполнителя (процессор автоматически выполняет программу, меняющую содержимое памяти).
Машина Поста — пример автоматического исполнителя с ограниченными возможностями; компьютер — универсальный автоматический исполнитель обработки информации.
Проверка понимания: возьми \(N = 21\). Тогда \(21 = 5\cdot 4 + 1\), \(n = 4\) — целое натуральное, значит машина гарантированно выигрывает. А при \(N = 20\): \(20 = 5\cdot 4\), остаток не 1, так что выигрыш не гарантирован.