МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка" Кафедра САПР
ЗВІТ до лабораторної роботи № 9 на тему: Машина Тьюрінґа Виконав: Гр. КН-214 Перевірив: Денисюк П. Ю. Львiв 2007 1. Мета: Вивчення машин Тюрінга. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI 2.4.1 Історія виникнення Алан Тьюрінг у 1936 році опублікував у працях Лондонського математичного товариства статтю «Про обчислювальні числа у застосуванні до проблеми розв’язуваності», яка разом із роботами Поста і Черча лежить в основі сучасної теорії алгоритмів. Передісторія створення цієї роботи пов’язана із формулюванням Давидом Гільбертом на Міжнародному математичному конгресі у Парижі у 1900 році нероз’язуваних математичних проблем. Однією з них була задача доведення несуперечності системи аксіом звичайної арифметики, яку Гільберт надалі уточнив як “проблему розв’язуваності” - знаходження загального методу для визначення виконуваності даного вислову на мові формальної логіки.
Рис.1 Алан Тьюрінг із колегами по Університету (крайній зліва) Стаття Тюрінга якраз і давала відповідь на цю проблему - друга проблема Гільберта виявилася нерозв’язуваною. Але значення статті Тюрінга виходило далеко за межі тієї задачі, з приводу якої вона була написана. Варто навести характеристику цієї роботи, що належить Джону Хопкрофту: “Працюючи над проблемою Гільберта, Тюрінгу довелося дати чітке визначення самого поняття методу. Відштовхуючись від інтуїтивного уявлення про метод як про певний алгоритм, тобто процедурі, яка може бути виконана механічно, без творчого втручання, він показав, як цю ідею можна втілити у вигляді точної моделі обчислювального процесу. Отримана модель обчислень, у якій кожний алгоритм розбивався на послідовність простих, елементарних кроків, і була логічною конструкцією, названою згодом машиною Тюрінга”. Машина Тюрінга є розширенням моделі кінцевого автомата, розширенням, що включає потенційно нескінченну пам’ять з можливістю переходу (рух) від оглядаючої в даний момент комірки до її лівого або правого сусіда. Алан Тьюрінг висловив припущення, що будь-який алгоритм в інтуїтивному значенні цього слова може бути представлений еквівалентною машиною Тюрінга. Це припущення відоме як теза Чорча–Тюрінга. Кожний комп’ютер може моделювати машину Тюрінга (операції перезапису комірок, порівняння і переходу до іншої сусідньої комірки з урахуванням зміни стану машини). Отже, він може моделювати алгоритми в будь-якому формалізмі, і з цієї тези виходить, що всі комп’ютери (незалежно від потужності, архітектури тощо) еквівалентні з погляду принципової можливості рішення алгоритмічних задач. 2.4.2 Структурна схема Машини Тьюрінга Структуру моделі машини Тюрінга, склад її блоків та їх взаємодію можна задати у вигляді наступної структурної схеми:
Рис.2 Структура моделі машини Тюрінга На цій схемі відображено розділення пам’яті на зовнішню і внутрішню. Зовнішня пам’ять зображена комірками нескінченної стрічки, які призначені для зберігання інформації, закодованої в символах зовнішнього алфавіту, внутрішня пам’ять - двома комірками для зберігання чергової команди: q-комірка зберігає знак стану і p- комірка - знак зсуву. У цих двох комірках відбувається затримка знаків qs і r, отриманих на виході логічного блоку L в даному такті роботи, до початку наступного такту. З q- комірка по лінії зворотного зв'язку у логічний блок L поступає знак стану qj, вироблений цим же блоком на попередньому такті. З p- комірка знак зсуву прямує у механізм зсуву, керуючи переміщенням каретки. Логічний блок "спілкується" із зовнішньою пам'яттю за допомогою читаючої і записуючої головки (каретки); головка на схемі зображена прямокутником, встановленим проти "оглядаючого комірки". Ми можемо описати машину Тьюрінга використовуючи 4-х позиційний кортеж. На рис.3 представлено кортежі програми простої машини Тьюрінга. <s0, 1, s0, » >  < s0, 0, s1, 1 >  < s1, 1,...