ашин і розглядаються в якості однієї з можливих універсальних алгоритмічних систем. В
3. Алгоритмічна машина Посту
Насправді, Пост, на відміну від Тьюринга, не користувався терміном В«машинаВ», а називав свою модель алгоритмічної системою. Однак, підкреслюючи єдність підходів обох авторів, прийнято говорити про машину Посту.
Абстрактна машина Посту складається з нескінченної стрічки, розділеної на рівні секції, а також зчитувально-записуючої головки. Кожна секція може бути або порожній (тобто в неї нічого не записано), або заповнена (Відзначена, тобто в неї записана мітка). Вводиться поняття стан стрічки як інформація про те, які секції порожні, а які відзначені. По-іншому: стан стрічки - це розподіл міток по секціях, тобто це функція, яка кожному числовому номером секції ставить у відповідність або мітку, або знак В«порожньоВ». Природно, в процесі роботи машини стан стрічки змінюється. Стан стрічки і інформація про становище головки характеризують стан машини Посту.
Домовимося позначати головку знаком «» над оглядає, секцією, а мітку - знаком В«M В» усередині секції. Пуста секція ніякого знака не містить. За один такт (його називають кроком) голівка може зрушитися на одну секцію вправо або вліво і поставити або видалити мітку. Робота машини Посту полягає в переході від одного стану машини до іншого відповідно до заданої програми, яка будується з окремих команд. Кожна команда має структуру xKy, де:
- x - номер виконуваної команди;
- K - вказівка ​​про виконуваному дії;
- y - номер наступної команди (спадкоємця). p> Система команд машини, що включає шість дій, представлена ​​в таблиці 1. br/>
Таблиця 1 - Система команд машини Посту
№ п/п
Команда
Запис команди
Опис дій машини
1
Крок вправо
x в†’ y
Зрушення головки на одну секцію вправо
2
Крок вліво
x в†ђ y
Зрушення головки на одну секцію вліво
3
Встановити мітку
xMy
У оглядається секцію ставиться мітка
4
Стерти
мітку
xCy
З оглядає, секції видаляється мітка
5
Передача управління
В
За відсутності мітки в оглядається секції управління передається команді y 1 , за наявності - команді y 2
6
Зупинка
x стоп
Припинення роботи машини
Даний перелік має бути доповнений наступними умовами:
- команда xMy може бути виконана тільки в порожній секції;
- команда xCy може застосовуватися тільки до заповненої секції;
- номер спадкоємця будь-якої команди y повинен відповідати номеру команди, обов'язкової наявної в даній програмі. p> Якщо дані умови не виконуються, відбувається безрезультатна зупинка машини, тобто зупинка до отримання запланованого результату. На відміну від цієї ситуації, зупинка по команді x стоп є результативною, тобто вона відбувається після того, як результат дії алгоритму отриманий. Крім того, можлива ситуація, коли машина не зупиняється ніколи. Це відбувається, якщо жодна з команд не містить у якості послідовника номери команди зупинки або програма не переходить до цій команді.
Ще одним вихідним міркуванням є наступне: оскільки знаки будь-якого кінцевого алфавіту можуть бути закодовані цифрами, перетворення вихідного слова може бути представлено у вигляді деяких правил обробки чисел. З цієї причини в машині Посту передбачається тільки запис (Подання) цілих позитивних чисел. p> Ціле число k записують ється на стрічці машини Посту допомогою k +1 наступних підряд відмічених секцій, тобто застосовується унарна система числення. Сусідні запису чисел на стрічці розділяються однією або декількома порожніми секціями. p> Нижче наведено приклад запису чисел 0, 2 і 3.
M
M
M
M
M
M
M
M
Коло обчислювальних завдань, що вирішуються за допомогою машини Посту, вельми широкий. Однак, як зазначалося вище, на рівні елементарних кроків все зводиться до постановки або видалення мітки і зрушенню головки. В якості прикладів розглянемо кілька завдань, традиційно обговорюваних при освоєнні машин...
