lab02_Mashyna_Tjuringa_10_11_2009_print

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

Машина Тьюрінґа

МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 2

з курсу "Алгоритми і структури даних" для студентiв базового напрямку 6.050101 "Комп'ютернi науки"

Затверджено на засiданнi кафедриСистеми автоматизованого проектування"

Протокол N 2 вiд 4.09.2009р.

Львiв – 2009

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

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

2

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

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

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

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

2.1. Формалізація поняття алгоритму

Формалізація поняття алгоритму реалізується за допомогою побудови

алгоритмічних моделей. Можна виділити три основні типи універсальних алгоритмічних моделей:

рекурсивні функції (поняття алгоритму пов'язується з обчисленнями і числовими функціями)

машини Тюрінґа (алгоритм представляється як опис процесу роботи деякої гіпотетичної машини, здатної виконувати лише невелике число простих операцій)

нормальні алгоритми Маркова (алгоритм описується як перетворення слів над довільним алфавітом).

Істотно, що всі алгоритмічні моделі описують один і той же клас процесів. Доведено, що одні моделі зводяться до інших

2.2. Машина Тьюрінґа

2.2.1. Історія виникнення

Англійський математик Алан Тьюрінґ у 1936 році опублікував у працях Лондонського математичного товариства статтю «Про обчислювальні числа у застосуванні до проблеми розв’язуваності», яка разом із роботами Поста і Черча лежить в основі сучасної теорії алгоритмів.

Передісторія створення цієї роботи пов’язана із формулюванням Давидом Гільбертом на Міжнародному математичному конгресі у Парижі у

3

1900 році нероз’язуваних математичних проблем. Однією з них була задача доведення несуперечності системи аксіом звичайної арифметики, яку Гільберт надалі уточнив як “проблему розв’язуваності” – знаходження загального методу для визначення виконуваності даного вислову на мові формальної логіки. Стаття Тюрінґа була присвячена вирішенню цієї проблеми.

Рис.2.1. Алан Тьюрінґ із колегами по Університету (крайній зліва)

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

Алан Тьюрінґ висловив припущення, що будь-який алгоритм в інтуїтивному значенні цього слова може бути представлений еквівалентною машиною Тюрінґа. Це припущення відоме як теза Чорча–Тюрінґа. Кожний комп’ютер може моделювати машину Тюрінґа (операції перезапису комірок,

порівняння і переходу до іншої сусідньої комірки з урахуванням зміни стану машини). Отже, він може моделювати алгоритми в будь-якому формалізмі, і

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

4

2.2.2. Структурна схема Машини Тьюрінґа

Структурна схема моделі машини Тюрінґа наведена на рис.2.2.

Рис.2.2. Структурна схема моделі машини Тюрінґа

На схемі (рис.2.2) відображено розділення пам’яті на зовнішню і внутрішню. Зовнішня пам’ять зображена комірками нескінченної стрічки, які призначені для зберігання інформації, закодованої в символах зовнішнього алфавіту. Внутрішня пам’ять - двома комірками для зберігання чергової команди: q-комірка зберігає знак стану і p- комірка - знак зсуву. У цих двох комірках відбувається затримка знаків qs і r, отриманих на виході логічного блоку L в даному такті роботи, до початку наступного такту. З комірки q по лінії зворотного зв’язку у логічний блок L поступає знак стану qj, вироблений цим же блоком на попередньому такті. З комірки p знак зсуву – керує переміщенням каретки.

Логічний блок "спілкується" із зовнішньою пам’яттю за допомогою читаючої і записуючої головки (каретки). Головка на схемі (рис2.2.)

зображена стрілкою, встановленою проти "поточної комірки".

5

Можна описати машину Тьюрінґа використовуючи 4-х позиційний кортеж. На рис.2.3 представлено кортежі програми простої машини Тьюрінґа.

<s0, 1, s0, » >

<s0, 0, s1, 1 >

<s1, 1, s1, « >

<s1, 0, s2, » >

Рис.2.3. Приклад програми машини Тьюрінґа

У випадку необхідності дослідження поведінки машини Тьюрінґа використовують діаграми станів. На рис. 2.4 зображено приклад машини Тьюрінґа у вигляді діаграми станів (для програми наведеної на рис.2.3).

Рис.2.4. Діаграма станів машини Тьюрінґа

На рис.2.4 стани представлені у вигляді кіл. Початковий стан представлений подвійном колом. Переходи зображаються стрілками, які виходять з одного кола і заходять у друге (можливо то саме) коло. Стрілки підписуються парою символів. Перший символ – символ, який має бути прочитаний і перенесений головкою запису/зчитування (стрілкою), а другий символ – дія, яка буде виконана після того як відбувся перехід. Дія буде або

6

символом, який має бути записаний, або стрілка, яка вказує переміщення вправо чи вліво.

Наприклад, якщо ми збираємося спроектувати машину, яка виконуватиме додавання, тоді нам потрібно описати інтерпретацію одиниць і нулів, які з’являтимуться на стрічці. У прикладі представимо число n як блок із n+1 копій символу ‘1’ на стрічці. Таким чином цифра 0 буде відображати одна ‘1’, а цифру 3 – блок із чотирьох ‘1’.

Зробимо наступне припущення, що якщо функція, яка має бути обчислена вимагає n аргументів, тоді машина Тьюрінґа починатиме виконання алгоритму із найлівішого положення головки запису/зчитування.

Блоки одиниць, які представляють аргументи мають бути відокремлені одним символом ‘0’. Наприклад, для обчислення суми 3+4, машина Тьюрінґа почне виконання алгоритму у наступній конфігурації (рис.2.5), де три крапки означають нулі, які ми не можемо побачити на безмежній стрічці, а стрілка вказує на комірку, яка зчитується у даний момент.

Рис.2.5. Початкова конфігурація для операції додавання

Машина повинна закінчити виконання алгоритму у стандартній конфігурації. На стрічці повинен бути єдиний блок ‘1’, і машина повинна зчитувати найлівішу ‘1’ (початкова конфігурація). Якщо машина коректно обчислила функцію, тоді цей блок повинен представляти правильний результат. Отже, машина, яка виконує операцію додавання, розпочавши із початкової конфігурації (рис.2.5) повинна завершити роботу у конфігурації,

що зображена на рис.2.6.

7

Ця машина нагадує машину знаходження наступного елементу (рис.4) у

присутності переходу іх стану s0 у стан s2 , тому що машина має вписати ‘1’

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

машина повинна об’єднати два блоки ‘1’ у один блок, який містить

(n+1)+1+(m+1) копій символу ‘1’, тому, перейшовши у стан s2 стрічка представляє число n+m+2. Для виправлення результату необхідно перемістити дві копії ‘1’, які отримуються у станах s2 і s3, кожний з яких замінює ‘1’ нулями і тоді пересуває головку у крайнє ліве положення.

Оскільки стрічка початково містить принаймні дві ‘1’ і ми маємо дописати ще одну, тому стирання двох ‘1’ залишить принаймні одну на стрічці у кінці обчислень, і ми прочитаємо всі до крайної лівої позиції.

2.2.3. Конфігурації роботи машини Тьюрінґа

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

символами на стрічці і коміркою, яка у даний момент зчитується. Опис цих трьох даних називається миттєвим описом конфігурації обчислень. Графічне представлення такого опису представлено на рис.2.8, у якому стрілка показує на скановану у даний момент часу комірку, а назва стану вказана поруч із стрілкою.

Рис.2.8. Миттєва конфігурація обчислень машини Тьюрінґа

2.4.4. Формулювання визначення машин Тьюрінґа

Існує кілька варіантів формулювання машини Тьюрінґа, які є еквівалентними до розглянутого. Оскільки всі визначення машини Тьюрінґа

9

еквівалентні одне одному, то ми можемо вибрати серед цих формулювань будь-яке, що нам найбільше підходить.

Формулювання F1 і формулювання F2 є еквівалентними якщо для будь-

якої описаної у формулюванні F1 існує машина, описана у F2 яка має ту саму поведінку введення-виведення, і навпаки, наприклад, коли розпочинає обчислення з тієї самої комірки на стрічці і завершує роботи на тій самій стрічці у тій самій комірці.

Безмежні двосторонні стрічки

У початково наведеному формулюванні визначено, що стрічка має кінець, скажімо зліва, і є безмежною вправо. Якщо припустити, що стрічка буде безмежною, як у правому напрямку, так і у лівому, то це призведе до нового формулювання машини Тьюрінґа, еквівалентне першому. Для будь-

якої машини Тьюрінґа, яка використовує двосторонню безмежну стрічку існує машина Тьюрінґа з односторонньою безмежною стрічкою із однаковою поведінкою при введенні/виведенні, і навпаки.

Двохвимірні стрічки

Замість одновимірної безмежної стрічки можна розглядати двохвимірну

“стрічку”, яка простягається безмежно вгору і вниз, так само як у ліво і вправо. Ми додамо до визначення, що машинна може переміщати головку читання-запису вгору і вниз на одну комірку. Дане формулювання знову є еквівалентним початковому.

Довільний рух головки

Модифікуючи визначення машини Тьюрінґа у моменті руху головки читання-запису на довільну кількість комірок у визначеному напрямку не змінює поняття машини Тьюрінґа.

Довільна кількість головок читання-запису

Машина Тьюрінґа може мати довільну кількість головок читання-

запису. Це також не змінює поняття машини Тьюрінґа.

10