мітки.
. Умовний перехід по мітці.
. STOP - зупинка (завершення роботи машини Посту);
Для роботи машини потрібно задати програму і її початковий стан (тобто стан стрічки і позицію каретки). Після запуску можливі варіанти:
робота може закінчитися нездійсненним командою (стирання неіснуючої мітки або запис в позначене поле);
робота може закінчитися командою Stop;
робота ніколи не закінчиться.
ОПИС РОБОТИ МАШИНИ ПОСТУ
абстрактний обчислювальний машина автомат
Абстрактна (тобто існуюча не реально, а лише в уяві) машина Посту, призначена для доказів різних тверджень про властивості програм. Дана машина являє собою універсальний виконавець, який є повністю детермінованим, що дозволяє «вводити» початкові дані, і після виконання програм «читати» результат. Машина Поста менш популярна, ніж машина Тьюринга, хоча вона значно простіше неї. З її допомогою можна вести навчання першого навичкам складання програм для ЕОМ. Машина Поста являє собою нескінченну стрічку, розділену на однакові клітини, кожна з яких може бути або порожній, або заповненої міткою «V», і головки, яка може переміщатися уздовж стрічки на одну клітку вправо або вліво, наносити в клітку стрічки мітку, якщо цією мітки там раніше не було, прати мітку, якщо вона була, або перевіряти наявність у клітці мітки. Інформація про заповнених мітками клітинах стрічки характеризує стан стрічки, яке може змінюватися в процесі роботи машини. У кожен момент часу головка («-») знаходиться над однією з клітин стрічки. Інформація про місця розташування головки разом із станом стрічки характеризує стан машини Посту.
Ситуації, в яких головка повинна завдавати мітку там, де вона вже є, або, навпаки, прати мітку там, де її немає, є аварійними (неприпустимими) і викликають останов.
Програмою для машини Посту називається непорожній список команд, такий що:
) на п-му місці команда з номером n;
) номер т кожної команди збігається з номером якої-небудь команди списку.
Останов машини Посту може бути викликаний декількома причинами:
) останов по команді «стоп»; такий останов називається результативним і вказує на коректність алгоритму (програми);
) останов при виконанні неприпустимою команди; в цьому випадку останов називається безрезультативним;
) машина не зупиняється ніколи; в такому випадку ми маємо справу з некоректним алгоритмом (програмою).
Число k представляється на стрічці машини Посту йдуть підряд k + 1 мітками, одна мітка означає число «0». Між двома числами робиться інтервал як мінімум з одним порожнім секції на стрічці.
опис алгоритмів
Розроблена в результаті виконання курсового проекту програма повинна буде представляти собою модель машини Посту на ЕОМ. Програма буде розроблятися на мові Турбо Паскаль і реалізовуватиме шість команд машини Посту. Початковий стан стрічки, місце головки і послідовність виконання команд будуть зчитуватися програмою з текстового файлу. Перший рядок текстового файлу містить послідовність нулів і один...
