Курсовая работа: Обучающая программа по информатике

Информация о том, какие секции пусты, а какие отмечены и где стоит каретка, образует состояние машины Поста.

Таким образом, состояние машины слагается из состояния ленты и указания номера той секции, которую обозревает каретка. За единицу времени (которую мы будем называть шагом) каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может поставить (напечатать) или уничтожить (стереть) метку на той секции, против которой она стоит, а также распознать, стоит или нет метка в обозреваемой ею секцией[2].

Программа машины Поста

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

Каждая программа машины Поста состоит из команд. Командой машины Поста будем называть выражение, имеющее один из следующих шести видов (буквы i, j, j₁ , j₂ означают всюду натуральные числа 1, 2, 3, 4, 5, …):

Первый вид. Команды движения вправо.

Второй вид. Команды движения влево.

Третий вид. Команды печатания метки.

Четвертый вид. Команды стирания метки.

Пятый вид. Команды передачи управления.

Шестой вид. Команды остановки.

Например,

является командой движения вправо,

- командой передачи управления, а

-командой остановки.

Число i, стоящее в начале команды, называется номером команды. Так, у приведенных только что команд номера соответственно 137, 25 и 6386. Число j, стоящее в конце команды (а у команд передачи управления - каждое из чисел j₁ , и j₂ ), будем называть отсылкой (при этом в команде передачи управления j₁ —верхней, а j₂ — нижней отсылкой). У команд остановки нет отсылки. Так, у приведенных только что команд отсылками служат числа 1, 32, 25, причем 32 —верхняя отсылка, а 25 — нижняя отсылка.

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

1) На первом месте в этом списке стоит команда с номером 1, на втором месте (если оно есть) – команда с номером 2 и т. д.; вообще на k-м месте стоит команда с номером k.

2) Отсылка любой из команд списка совпадает с номером некоторой (другой или той же самой) команды списка (более точно: для каждой отсылки каждой команды списка найдется в.списке такая команда, номер которой равен рассматриваемой отсылке).

Например, следующий список будет программой машины Поста:

А эти два с