Lab01_Mashyna_Posta_07_11_2009_print

МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет «Львiвська полiтехнiка»

МАШИНА ПОСТА

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторної роботи № 1 з курсу «Алгоритми і структури даних»

для студентiв базового напрямку 6.050101 «Комп’ютернi науки»

Затверджено на засiданнi кафедри «Системи автоматизованого проектування» Протокол N 2 вiд 4.09.2009р.

Львiв – 2009

Машина Поста: Методичні вказівки до лабораторної роботи N1 з курсу «Алгоритми і структури даних» для студентiв базового напрямку 6.050101 «Комп’ютернi науки» / Укл.: А.Б.Керницький, П.Ю.Денисюк, М.Р.Мельник. - Львiв: Національний університет «Львівська політехніка», 2009.- 16 с.

Укладачі	Керницький А.Б., др.інж., ст. викл.,
	Денисюк П.Ю., канд.техн.наук, ст. викл.,
	Мельник М.Р., асист.

Відповідальний за випуск Лобур М.В., д-р техн.наук, проф.

Рецензенти	Каркульовський В.І., канд.техн.наук, доц.
	Яковина В.С., канд.фіз.-мат.наук, доц.

2

1. МЕТА РОБОТИ

Мета роботи – вивчення формального визначення поняття алгоритму,

пов’язаного із введеною Емілем Постом спеціальної математичної конструкції (машина Поста) і постулюванням тези про еквівалентність такого формалізму і поняття «алгоритм».

2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI

Однією із фундаментальних статей, результати якої лежать в основі сучасної теорії алгоритмів, є стаття польсько-американського математика і логіка Еміля Леона Поста (1897-1954), «Finite combinatory processes - Formulation 1» [1], опубліковану у 1936 році. У ній він запропонував абстрактну обчислювальну конструкцію, яка дозволила вперше уточнити поняття алгоритму і яку згодом назвали машиною Поста. При розробці обчислювальної конструкції Пост керувався принципом створення максимально простої абстракції: мінімум операцій під час обробки інформації, вхідна інформація повинна бути закодованою з використанням мінімального набору символів.

Не дивлячись на примітивність машини Поста, будь-який існуючий алгоритм може бути записаний у вигляді програми для машини Поста. У

теорії алгоритмів існує так звана «теза Поста»: «Будь-який алгоритм можна представити у вигляді машини Поста». Ця теза одночасно є і формальним визначенням алгоритму. Алгоритм (за Постом) - програма для машини Поста, що приводить до вирішення поставленої задачі.

Теза Поста є гіпотезою. Її неможливо строго довести (так само, як і теза Тюрінга), тому що у ній фігурують, з одного боку, інтуїтивне поняття

«будь-який алгоритм», а з іншого боку - точне поняття «машина Поста». Для того, щоб спростувати гіпотезу Поста, необхідно придумати алгоритм, який

3

неможливо записати у вигляді програми для машини Поста. На сьогоднішній день такого алгоритму не існує.

Машина Поста — це абстрактна (тобто така, що не існує в арсеналі техніки), але дуже проста обчислювальна машина. Машина Поста, не дивлячись на зовнішню простоту, може здійснювати різні обчислення, для чого потрібно задати початковий стан каретки і програму, яка виконає ці обчислення. Машиною ця математична конструкція названа тому, що при її побудові використовуються деякі поняття реальних машин (елемент пам’яті,

команда тощо). Машину Поста можна розглядати як спрощену модель комп’ютера. Насправді, як комп’ютер, так і машина Поста мають:

неподільні носії інформації (комірки — біти), які можуть бути заповненими або незаповненими;

обмежений набір елементарних дій — команд, кожна з яких

виконується за один такт (крок).

Обидві машини працюють на основі програми. Проте у машині Поста інформація розташовується лінійно і читається підряд, а в комп’ютері можна читати інформацію за адресою; набір команд комп’ютера значно ширший і виразніший за команди машини Поста.

2.1. Склад машини Поста

Машина Поста складається із стрічки та каретки (яка також називається головкою зчитування/запису). Стрічка є безмежною і розділена на комірки однакового розміру (рис.2.1).

Рис. 2.1. Каретка завжди вказує на одну із комірок

4

Комірка стрічки може бути порожньою, або у ній може перебувати мітка

V. Інформація про те, які комірки порожні, а які містять мітки, утворює стан стрічки. Іншими словами, стан стрічки — це розподіл міток по комірках.

Стан стрічки змінюється у процесі роботи машини. Зауважимо, що наявність міток у комірці можна інтерпретувати як «1», а відсутність як «0». Таке двійкове представлення інформації подібне до уявлення, яке використовується практично у всіх сучасних комп’ютерах.

Каретка може пересуватися вздовж стрічки вліво і вправо. Коли вона нерухома — вона перебуває навпроти однієї комірки стрічки. У такому випадку говорять, що каретка оглядає одну комірку. За одиницю часу каретка може зробити одну із трьох дій: стерти мітку, поставити мітку, зробити рух до сусідньої комірки. Стан машини Поста складається із стану стрічки і розташування каретки.

Дії каретки підпорядковані програмі, яка складається з пронумерованого набору команд (команди можна представляти як рядки програми). Команди бувають шести типів:

1.записати 1 (мітку), перейти до i-го рядка програми;

2.записати 0 (стерти мітку), перейти до i-го рядка програми;

3.переміститися вліво, перейти до i-го рядка програми;

4.переміститися вправо, перейти до i-го рядка програми;

5.зупинка;

6.якщо 0, то перейти до i-го рядка програми, інакше перейти до j-го рядка програми.

Наведемо перелік неприпустимих дій, які ведуть до аварійної зупинки машини:

спроба записати 1 (мітку) в заповнену комірку;

спроба стерти мітку в порожній комірці;

нескінченне виконання (зациклення).

5

2.2. Графічне представлення команд машини Поста

Графічне представлення команд машини Поста наведено в таблиці 1.

Таблиця 1.

	Графічне представлення команд машини Поста
→	Крок вправо
←	Крок вліво
V	Записати мітку
X	Стерти мітку
? a: b	Переглянути комірку: якщо в комірці знаходиться 0, тоді
	перейти на команду з номером а, інакше на команду з
	номером b.
!	Зупинка

Будемо розуміти, що ми можемо застосувати програму до біжучого стану машини Поста, якщо виконання програми не призведе до зациклювання, тобто рано чи пізно ми виконаємо команду «Зупинка».

Програмою для машини Поста називається непорожній список послідовно пронумерованих команд наступної структури: n K m,

де n - порядковий номер команди, K − дія, яка виконується кареткою, m - номер наступної команди, яку необхідно виконати.

З погляду властивостей алгоритмів, що вивчаються за допомогою машини Поста, найбільший інтерес представляють причини зупинки машини під час виконанні програми:

зупинка за командою «стоп». Така зупинка називається результативною і вказує на коректність алгоритму;

зупинка при виконанні неприпустимої команди. У цьому випадку зупинка називається безрезультатною;

машина не зупиняється ніколи. У цьому і у попередньому випадку ми маємо справу з некоректним алгоритмом.

6

Під початковим станом каретки розумітимемо її положення навпроти порожньої комірки лівіше за найлівішу мітку на стрічці.

Приклад 1. На стрічці в одній з комірок поставлена мітка (решта комірок є порожніми). Каретка стоїть на деякій відстані лівіше за цю комірку.

Потрібно підвести каретку до комірки, стерти мітку і зупинити каретку зліва від цієї комірки.

Розв’язок. Спочатку спробуємо описати алгоритм звичайною мовою.

Оскільки нам відомо, що каретка стоїть навпроти порожньої комірки, але невідомо, скільки кроків потрібно зробити до заповненої комірки, ми можемо відразу зробити крок вправо; перевірити, чи заповнена комірка; якщо вона порожня, то повторювати ці дії доти, поки не наштовхнемося на заповнену комірку. Щойно ми її знайдемо, ми виконаємо операцію стирання, після чого потрібно буде лише змістити каретку вліво і зупинити виконання програми.

Програма пошуку і стирання єдиної мітки на стрічці для машини Поста має наступний вигляд:

1.→ 2

2.? 1: 3

3.X 4

4.← 5

5.!

2.3.Представлення чисел і операції над ними

Число k представляється на стрічці машини Поста k+1 мітками, які йдуть підряд (одна мітка означає цифру «0»). Між двома числами робиться інтервал як мінімум з однієї порожньої комірки на стрічці. Наприклад, запис чисел 3 і 5 на стрічці машини Поста виглядатиме наступним чином рис.2.2.

Рис.2.2. Запис чисел 3 і 5 на стрічці машини Поста

7

Зауважимо, що використана в машині Поста система числення є

непозиційною.

Приклад 2. Складемо програму для додавання одиниці до довільного

числа. Припустимо, що на стрічці записано лише одне число 4 і каретка

розташована лівіше від найлівішої одиниці (в початковому стані).

Рис.2.3. Збільшення числа на одиницю

Для вирішення задачі можна перемістити каретку вправо до першої

порожньої комірки, а потім записати мітку.

Програма, яка додає до числа мітку справа, має вигляд (див.рис.2.4.)

1.→ 2

2.? 1: 3

3. V 4

4. !

Рис.2.4. Текст програми та результат виконання, яка додає до числа мітку справа

Програма, яка додає до числа мітку зліва наведена на рис. 2.5.

1.V 2

2.← 3

3.!

Рис.2.5. Текст програми та результат виконання, яка додає до числа мітку зліва

2.4.Визначення результату шляхом виконання програм.

Застосовність програм

Розглянемо ряд програм машини Поста.

Приклад 3. Визначити стан, в якому опиниться машина Поста в

результаті виконання програми при заданому початковому стані стрічки.

8

1) 1111101			1) 111111
2) 111111			2) 11101
			3) 101111
а)		5. → 6	б)		8. ← 2
1.	? 2: 4	6. ? 8: 7	1.	? 2: 3	9. ? 12: 10
2.	V 3	7. ← 6	2. !		10.	X 11
3. !		8. → 1	3.	→ 4	11.	→ 1
4.	X 5		4.	? 7: 5	12.	V 13
			5.	X 6	13.	← 1
			6.	→ 9
			7.	V 8

Пояснення: виділена цифра, наприклад 1, означає, що цю комірку каретка оглядає в початковий момент часу.

Розв’язок. Виділена цифра показує, на якій комірці зупиниться машина.

a) 1)	11000001	b) 1) 1100101
2)	11000001	2)	10001
		3)	111111

Приклад 4. Написати програми для машини Поста, які володіють наступними властивостями:

а) програма застосовна до будь-якого стану машини Поста;

б) програма не застосовна до жодного стану машини Поста, і зона роботи для будь-якого початкового стану — безмежна;

в) програма не застосовна до жодного стану машини Поста, і зона роботи для будь-якого початкового стану обмежена однією і тією ж кількістю комірок,

які не залежать від вибраного початкового стану стрічки.

9

Розв’язок:

а) програма, застосовна до будь-якого стану машин Поста: ! 1

б) програма, не застосовна до жодного стану машини Поста, і зона роботи будь-якого початкового стану — безмежна:

→1

в) програма не застосовна до жодного стану машини Поста, і зона роботи для будь-якого початкового стану обмежена однією і тією ж кількістю комірок,

які не залежать від вибраного початкового стану стрічки:

1.→ 2

2.← 1

2.5. Арифметичні задачі

Розглянемо ряд програм для машини Поста, які виконують

арифметичні дії.

Приклад 5. На стрічці заданий масив міток. Збільшити довжину масиву на 2 мітки. Каретка знаходиться або зліва від масиву, або над однією з

комірок масиву.
	Розв’язок.
1.	? 2: 3	(команди 1 і 2	— пересуваємо каретку до масиву)
2.	→ 1
3.	→ 4	(команди 3 і 4	— пересуваємо каретку до кінця масиву)
4.	? 5: 3
5.	V 6	(команди 5–7 — ставимо 2 мітки в кінець масиву)

6.→ 7

7.V 8

8.! (стоп)

10