ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2337
Скачиваний: 1
16
4)
Переміститися вправо на 1 ящик.
5)
Визначити чи має ящик позначку або ні, і за результатом перейти
на одну з двох зазначених інструкцій.
6)
Зупинитися.
Відзначимо, що 1 і 2 інструкції включають захист від невірних ситуацій.
Програма являє собою нумеровану послідовність інструкцій, причому
переходи в інструкції 5 проводяться на вказані в ній номери інших
інструкцій.
2.2 Фінітний 1 – процес
Програма (набір інструкцій у термінах Посту) є однією і тією ж для всіх
конкретних проблем.
Пост вводить такі поняття:
•
набір інструкцій застосовується до загальної проблеми, якщо для
кожної конкретної проблеми не виникає колізій в інструкціях 1 і 2,
тобто ніколи програма не стирає мітку в порожньому ящику і не
встановлює мітку в позначеному ящику;
•
набір інструкцій закінчується (за кінцеве кількість інструкцій), якщо
виконується інструкція (6);
•
набір інструкцій задає фінітний 1 – процес, якщо набір може бути
використаним, і закінчується для кожної конкретної проблеми;
•
фінітний 1 – процес для загальної проблеми є 1 – рішення, якщо
відповідь для кожної конкретної проблеми є правильною (це
визначається зовнішньою силою).
2.3 Спосіб завдання проблеми та формулювання 1
За Постом проблема задається зовнішньою силою шляхом позначки
кінцевою кількості ящиків стрічки.
Прийнято вважати, що машина працює в одиничній системі числення (0
= V; 1 = VV; 2 = VVV; 3 = VVV
V), тобто нуль представляється одним
поміченим ящиком, а ціле позитивне число – поміченими ящиками в
кількості на одиницю більше його значення.
17
Оскільки безліч конкретних проблем, що становлять загальну проблему
є рахунковим, то можна встановити взаємно однозначну відповідність
(биєктивне відображення) між множиною позитивних цілих чисел N і
множиною конкретних проблем.
Загальна проблема називається по Посту 1-заданой, якщо існує такий
фінітний 1 – процес, що, будучи, застосованим до n є N в якості вхідної
конфігурації ящиків, він задає n-ю конкретну проблему у вигляді набору
помічених ящиків.
Якщо загальна проблема 1-задана і 1-розв'язана, то, поєднуючи набори
інструкцій за завданням проблеми, і її вирішенням отримуємо відповідь за
номером проблеми. Це і є в термінах Посту формулювання 1.
Таким чином, гіпотеза Посту полягає в тому, що будь-які більш широкі
формулювання в сенсі алфавіту символів стрічки, набору інструкцій, подання
та інтерпретації конкретних проблем зводяться до формулювання 1.
гіпотеза
очевидно
Отже, якщо гіпотеза вірна, то будь-які інші формальні визначення, що
задають певний клас алгоритмів, еквівалентні класу алгоритмів, заданих
формулюванням 1 Еміля Посту.
2.4
Принцип роботи
Машина Поста складається з каретки (каретки, яка зчитує або записує) і
безмежної в обидві сторони смуги, що поділена на комірки (ящики). Кожна
комірка смуги може бути або порожньою – 0, або помічено міткою – 1. За
один крок каретка може переміститися на одну позицію вліво або вправо,
зчитати, поставити або стерти символ в тому місті, де вона стоїть. Робота
машини Посту визначається програмою, що складається з кінцевого числа
рядків.
Для роботи машини необхідно задати програму і її початковий стан
(тобто стан стрічки і позиції каретки). Кареткою управляє програма, що
складається з рядків команд. Кожна команда має наступний синтаксис:
Алгоритм
Програма Поста
Формулювання 1
18
i K j,
де i – номер команди,
K –
дія каретки,
j –
номер наступної команди (перехід).
Всього для машини Поста існує шість типів команд (див. рис. 2.2):
1 – V j –
поставити мітку, перейти до j-го рядка програми.
2 – X j –
витерти мітку, перейти до j-го рядка програми.
3 – <- j –
пересунуться вліво, перейти до j-го рядка програми.
4 – -> j –
пересунуться вправо, перейти до j-го рядка програми.
5 – ? j1; j2 –
якщо комірка немає мітки, то перейти до j1-го рядка
програми, інакше перейти до j2-го рядка програми.
6 – ! –
кінець програми (стоп).
У команди «стоп» посилань нема.
Після запуску можливі варіанти:
•
робота може закінчитися командою, що не виконується (витирання
існуючою мітки або записування в помічене поле);
•
робота може закінчитися командою Stop;
•
робота ніколи не закінчиться.
19
Рис. 2.2. Шість команд машини Поста.
20
У кожен момент часу каретка («-») знаходиться над однією з клітин
стрічки і, як кажуть, обдивляється її. Інформація про місця розташування
каретки разом із станом стрічки характеризує стан машини Посту рис. 2.3.
«-»
Рис. 2.3. Стан машини Посту.
Ситуації, в яких каретка повинна наносити мітку там, де вона вже є, або
навпаки, витирати мітку там, де її немає, є аварійними (недопустимими).
Програмою для машини Поста називають не порожній список команд,
такій, що :
−
на n-м місті команда с номером n;
−
номер кожної команди співпадає з номером будь-якої команди
списку.
З точки зору властивостей алгоритмів, що вивчаються за допомогою
машини Посту, найбільший інтерес представляють причини зупинки машини
при виконанні програми:
−
останов по команді "стоп". Такій останов називається
результативним і вказує на коректність алгоритму (програми);
−
останов при виконанні неприпустимою команди. В цьому
випадку останов називається без результативним;
−
машина не зупиняється ніколи. У цьому і в попередньому
випадку ми маємо справу з некоректним алгоритмом (програмою).
Будемо розуміти під початковим станом каретки її становище проти
порожньої клітини лівіше найлівішої мітки на стрічці.
Число k представляється на стрічці машини Посту (k + 1) мітками, що
йдуть підряд. Одна мітка означає число «0». Між двома числами робиться
інтервал як мінімум з однієї порожньої секції на стрічці.
Наприклад, запис чисел 3 і 5 на стрічці машини Посту буде виглядати
так: