МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР Машина Тьюрінґа Звіт до лабораторної роботи № 2 з курсу «Теорія алгоритмів» для студентiв базового напрямку 6.050101 «Комп’ютернi науки» 1. Мета роботи Мета роботи – вивчення формального визначення поняття алгоритму, пов’язаного із введеною Аланом Тьюрінґом спеціальної математичної конструкції (машина Тьюрінга) і постулювання тези про еквівалентність такого формалізму і поняття «алгоритм» 2. Теоретичні відомості Формалізація поняття алгоритму Формалізація поняття алгоритму реалізується за допомогою побудови алгоритмічних моделей. Можна виділити три основні типи універсальних алгоритмічних моделей:  рекурсивні функції (поняття алгоритму пов'язується з обчисленнями і числовими функціями)  машини Тюрінґа (алгоритм представляється як опис процесу роботи деякої гіпотетичної машини, здатної виконувати лише невелике число простих операцій)  нормальні алгоритми Маркова (алгоритм описується як перетворення слів над довільним алфавітом). Істотно, що всі алгоритмічні моделі описують один і той же клас процесів. Доведено, що одні моделі зводяться до інших. На схемі відображено розділення пам’яті на зовнішню і внутрішню. Зовнішня пам’ять зображена комірками нескінченної стрічки, які призначені для зберігання інформації, закодованої в символах зовнішнього алфавіту. Внутрішня пам’ять - двома комірками для зберігання чергової команди: q-комірка зберігає знак стану і p- комірка - знак зсуву. У цих двох комірках відбувається затримка знаків qs і r, отриманих на виході логічного блоку L в даному такті роботи, до початку наступного такту. З комірки q по лінії зворотного зв’язку у логічний блок L поступає знак стану qj, вироблений цим же блоком на попередньому такті. З комірки p знак зсуву – керує переміщенням каретки. Логічний блок "спілкується" із зовнішньою пам’яттю за допомогою читаючої і записуючої головки (каретки). Головка на схемі (рис2.2.) зображена стрілкою, встановленою проти "поточної комірки". Можна описати машину Тьюрінґа використовуючи 4-х позиційний кортеж. 3. Індивідуальне завдання Варіант 10 На інформаційній стрічці машини Тюрінґа в трьох секціях в довільному порядку записані 3 різних букви: A, B і C. Каретка в стані q0 оглядає букву, розташовану справа. Необхідно скласти функціональну схему машини Тюрінґа, яка зуміє поміняти місцями крайні букви. 4. Текст програми
5. Результати обчислень
6.Висновок На даній лабораторній роботі ми вивчили формальне визначення поняття алгоритму, пов’язаного із введеною Аланом Тьюрінґом спеціальної математичної конструкції (машина Тьюрінга) і постулюванням тези про еквівалентність такого формалізму і поняття «алгоритм».