МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний аерокосмічний університет ім. М. Є. Жуковського
«Харківський авіаційний інститут»
Факультет радіоелектроніки, комп’ютерних систем та інфокомунікацій
Кафедра радіоелектронних та біомедичних комп’ютеризованих засобів і технологій
РЕФЕРАТ
з дисципліни «Теорія алгоритмів»
на тему «Машина Тюрінга, як моделі сучасних обчислювачів»
Виконав: студент 2 курсу групи 5-92кн/с
напряму підготовки (спеціальності)
122 Комп’ютерні науки
_Іванов Д. К. ____________
(прізвище й ініціали студента)
Прийняв: доцент кафедри 502, доцент
к.т.н., Довнар О. Й.
(посада, науковий ступінь, прізвище й ініціали)
Національна шкала: __________
Кількість балів: _____
Оцінка: ECTS _____
Харків – 2020
ЗМІСТ
| Вступ | 3 |
| Опис машини Тьюринга | 4 |
| Властивості машини Тьюринга як алгоритму | 6 |
| Машина Тьюринга і алгоритмічно нерозв'язні проблеми | 7 |
| Висновки | 10 |
| Перелік джерел посилань | 15 |
ВСТУП
Машина Тьюринга - це дуже просте обчислювальний пристрій. Вона складається з стрічки нескінченної довжини, розділеної на комірки, і головки, яка переміщується вздовж стрічки і здатна читати і записувати символи. Також у машини Тьюринга є така характеристика, як стан, який може виражатися цілим числом від нуля до деякої максимальної величини. Залежно від стану машина Тьюринга може виконати одну з трьох дій: записати символ у клітинку, пересунутися на одну клітинку вправо або вліво і встановити внутрішній стан.
Пристрій машини Тьюринга надзвичайно просто, проте на ній можна виконати практично будь-яку програму. Для виконання всіх цих дій передбачена спеціальна таблиця правил, в якій прописано, що потрібно робити при різних комбінаціях поточних станів і символів, прочитаних з стрічки.
У 1947 р Алан Тьюринг розширив визначення, описавши "універсальну машину Тьюринга". Пізніше для вирішення певних класів задач була введена її різновид, яка дозволяла виконувати не одну задачу, а кілька.
1. ОПИС МАШИНИ ТЬЮРИНГА
Алан Тьюринг (Turing) в 1936 році опублікував у працях Лондонського математичного товариства статтю "Про обчислюваних числах в додатку до проблеми дозволу", яка нарівні з роботами Посту і Черча лежить в основі сучасної теорії алгоритмів.
Передісторія створення цієї роботи пов'язана з формулюванням Давидом Гільбертом на Міжнародному математичному конгресі в Парижі в 1900 році недозволених математичних проблем. Однією з них була задача доказу несуперечності системи аксіом звичайної арифметики, яку Гільберт надалі уточнив як "проблему можливості розв'язання" - знаходження спільної методу, для визначення здійсненності даного висловлювання на мові формальної логіки.
Стаття Тьюринга якраз і давала відповідь на цю проблему - друга проблема Гільберта виявилася нерозв'язною. Але значення статті Тьюринга виходило далеко за рамки того завдання, з приводу якої вона була написана.
Наведемо характеристику цієї роботи, яка належить Джону Хопкрофта: "Працюючи над проблемою Гільберта, Тьюрингу довелося дати чітке визначення самого поняття методу. Відштовхуючись від інтуїтивного уявлення про метод як про якийсь алгоритм, тобто процедури, яка може бути виконана механічно, без творчого втручання , він показав, як цю ідею можна втілити в вигляді докладної моделі обчислювального процесу. Отримана модель обчислень, в якій кожен алгоритм розбивався на послідовність простих, елементарних кроків, і була логічною конструкцією, названої згодом машиною Тьюринга ".
Машина Тьюринга є розширенням моделі кінцевого автомата, розширенням, що включає потенційно нескінченну пам'ять з можливістю переходу (руху) від оглядається в даний момент осередку до її лівому або правому сусідові.
Формально машина Тьюринга може бути описана наступним чином. Нехай задані:
кінцеве безліч станів - Q, в яких може перебувати машина Тьюринга;
кінцеве безліч символів стрічки - Г;
функція δ (функція переходів або програма), яка задається відображенням пари з декартова твори Q x Г (машина знаходиться в стані qi і оглядає символ gi) в трійку декартова твори Q х Г х {L, R} (машина переходить в стан qi, замінює символ gi на символ gj і пересувається вліво або вправо на один символ стрічки) - Q x г -> Q х г х {L, R}
один символ з Г -> е (порожній);
підмножина Σ є Г - -> визначається як підмножина вхідних символів стрічки, причому е є (Г - Σ);
один зі станів - q0 є Q є початковим станом машини.
Розв'язувана проблема задається шляхом запису кінцевого кількості символів з безлічі Σ є Г - Si є Σ на стрічку:
eS1S2S3S4 ... ... ... Sne
після чого машина переводиться в початковий стан і головка встановлюється у самого лівого непорожньої символу (q0,w) -, після чого відповідно до зазначеної функції переходів (qi, Si) - -> (qj, Sk, L або R) машина починає замінювати оглядається символи, пересувати головку вправо або вліво і переходити в інші стани, запропоновані функцій переходів.
Зупинка машини відбувається в тому випадку, якщо для пари (qi, Si) функція переходу не визначена.
Алан Тьюринг висловив припущення, що будь-який алгоритм в інтуїтивному сенсі цього слова може бути представлений еквівалентної машиною Тьюринга. Це припущення відомо як теза Черча-Тьюринга. Кожен комп'ютер може моделювати машину Тьюринга (операції перезапису елементів, порівняння і переходу до іншої сусідньої осередку з урахуванням зміни стану машини). Отже, він може моделювати алгоритми в будь-якому формалізмі, і з цієї тези випливає, що всі комп'ютери (незалежно від потужності, архітектури і т.д.) еквівалентні з точки зору принципової можливості вирішення алгоритмічних задач.
2 ВЛАСТИВОСТІ МАШИНИ ТЬЮРИНГА ЯК АЛГОРИТМУ
На прикладі машини Тьюринга добре простежуються властивості алгоритмів. Попросіть учнів показати, що машина Тьюринга має всі властивості алгоритму.
Дискретність. Машина Тьюринга може перейти до (до + 1) - го кроку тільки після виконання кожного кроку, т.к саме кожен крок визначає, яким буде (до + 1) - й крок.
Зрозумілість. На кожному кроці в осередок пишеться символ з алфавіту, автомат робить один рух (Л, П, Н), і машина Тьюринга переходить в одне з описаних станів.
Детермінованість. У кожній клітині таблиці машини Тьюринга записаний лише один варіант дії. На кожному кроці результат визначений однозначно, отже, послідовність кроків вирішення завдання визначена однозначно, тобто якщо машині Тьюринга на вхід подають одне й те ж слово, то вихідний слово кожен раз буде одним і тим же.
Результативність. Змістовно результати кожного кроку і всієї послідовності кроків визначені однозначно, отже, правильно написана машина Тьюринга за кінцеве число кроків перейде в стан q0, тобто за кінцеве число кроків буде отримана відповідь на питання завдання.
Масовість. Кожна машина Тьюринга визначена над всіма можливими словами з алфавіту, в цьому і полягає властивість масовості. Кожна машина Тьюринга призначена для вирішення одного класу завдань, тобто для кожного завдання пишеться своя (нова) машина Тьюринга.
3. МАШИНА ТЬЮРИНГА І АЛГОРИТМІЧНО НЕРОЗВ'ЯЗНІ ПРОБЛЕМИ
За час свого існування людство придумало безліч алгоритмів для вирішення різноманітних практичних і наукових проблем. Задамося питанням - а чи існують які-небудь проблеми, для яких неможливо придумати алгоритми їх вирішення?
Твердження про існування алгоритмічно нерозв'язних проблем є досить сильним - ми констатуємо, що ми не тільки зараз на знаємо відповідного алгоритму, але ми не можемо принципово ніколи його знайти.
Успіхи математики до кінця XIX століття привели до формування думки, яке висловив Д. Гільберт - "в математиці не може бути нерозв'язних проблем", в зв'язку з цим формулювання проблем Гильбертом на конгресі 1900 року в Парижі була керівництвом до дії, констатацією відсутності рішень в даний момент.
Першою фундаментальною теоретичною роботою, пов'язаною з доказом алгоритмічної нерозв'язності, була робота Курта Геделя - його відома теорема про неповноту символічних логік. Це була строго формулювати математична проблема, для якої не існує вирішального її алгоритму. Зусиллями різних дослідників список алгоритмічно нерозв'язних проблем був значно розширений. Сьогодні прийнято при доказі алгоритмічної нерозв'язності деякої задачі зводити її до стала класичною завданню - "завданню зупинки".
Має місце бути наступна теорема: не існує алгоритму (машини Тьюринга), що дозволяє за описом довільного алгоритму і його вихідних даних (і алгоритм і дані задані символами на стрічці машини Тьюринга) визначити, чи зупиняється цей алгоритм на цих даних або працює нескінченно.
Таким чином, фундаментально алгоритмічна нерозв'язність пов'язана з нескінченністю виконуваних алгоритмом дій, тобто неможливістю передбачити, що для будь-яких вихідних даних рішення буде отримано за кінцеве кількість кроків.
Проте, можна спробувати сформулювати причини, що ведуть до алгоритмічної нерозв'язності, ці причини досить умовні, так як всі вони зводяться до проблеми зупинки, проте такий підхід дозволяє більш глибоко зрозуміти природу алгоритмічної нерозв'язності:
а) Відсутність загального методу розв'язання задачі
Проблема 1: Розподіл дев'яток в запису числа;
Визначимо функцію f (n) = i, де n - кількість дев'яток поспіль в десяткового запису числа, а i - номер самої лівої дев'ятки з n дев'яток поспіль: = 3,141592 ... f (1) = 5.
Завдання полягає в обчисленні функції f (n) для довільно заданого n.
Оскільки число є ірраціональним і трансцендентним, то ми не знаємо жодної інформації про розподіл дев'яток (так само як і будь-яких інших цифр) в десяткового запису числа. Обчислення f (n) пов'язане з обчисленням наступних цифр в розкладанні, до тих пір, поки ми не виявимо n дев'яток поспіль, однак у нас немає загального методу обчислення f (n), тому для деяких n обчислення можуть тривати нескінченно - ми навіть не знаємо в принципі (за природою числа) чи існує рішення для всіх n.
Проблема 2: Обчислення скоєних чисел;
Вчинені числа - це числа, які дорівнюють сумі своїх дільників, наприклад: 28 = 1 + 2 + 4 + 7 + 14.
Визначимо функцію S (n) = n-е за рахунком досконале число і поставимо задачу обчислення S (n) по довільно заданому n. Немає загального методу обчислення скоєних чисел, ми навіть не знаємо, безліч досконалих чисел звичайно або лічильно, тому наш алгоритм повинен перебирати всі числа підряд, перевіряючи їх на досконалість. Відсутність загального методу рішення не дозволяє відповісти на питання про зупинку алгоритму. Якщо ми перевірили М чисел при пошуку n-ого досконалого числа - чи означає це, що його взагалі не існує?
Проблема 3: Десята проблема Гільберта;
Нехай заданий многочлен n-го ступеня з цілими коефіцієнтами - P, чи існує алгоритм, який визначає, чи має рівняння P = 0 рішення в цілих числах?
Ю.В. Матіясевіч показав, що такого алгоритму не існує, тобто відсутня загальний метод визначення цілих коренів рівняння P = 0 по його цілочисельним коефіцієнтами.
б) Інформаційна невизначеність завдання
Проблема 4: Позиціонування машини Посту на останній позначений ящик;
Нехай на стрічці машини Посту задані набори помічених скриньок (кортежі) довільної довжини з довільними відстанями між кортежами і головка знаходиться у самого лівого поміченого ящика. Завдання полягає установці головки на самий правий позначений ящик останнього кортежу.
Спроба побудови алгоритму, вирішального цю задачу призводить до необхідності відповіді на питання - коли після виявлення кінця кортежу ми зрушили вправо по порожніх скриньок на М позицій і не виявили початок наступного кортежу - більше на стрічці кортежів немає або вони є десь правіше? Інформаційна невизначеність завдання полягає у відсутності інформації або про кількість кортежів на стрічці, або про максимальній відстані між кортежами - при наявності такої інформації (при дозволі інформаційної невизначеності) завдання стає алгоритмічно розв'язною.
в) Логічна нерозв'язність (в сенсі теореми Геделя про неповноту)
Проблема 5: Проблема "зупинки" (див. Теорема);
Проблема 6: Проблема еквівалентності алгоритмів;
По двох довільним заданим алгоритмам (наприклад, по двом машинам Тьюринга) визначити, чи будуть вони видавати однакові вихідні результати на будь-яких вихідних даних.
Проблема 7: Проблема тотальності;
За довільним заданим алгоритмом визначити, чи буде він зупинятися на всіх можливих наборах вихідних даних. Інша формулювання цього завдання - є чи частковий алгоритм Р всюди певним?
ВИСНОВКИ
Теорія складності також класифікує і складність самих проблем, а не тільки складність конкретних алгоритмів вирішення проблеми. Теорія розглядає мінімальний час і обсяг пам'яті, необхідні для вирішення найважчого варіанта проблеми на теоретичному комп'ютері, відомому як машина Тьюринга. Машина Тьюринга являє собою кінцевий автомат з нескінченною стрічкою пам'яті для читання записи і є реалістичною моделлю обчислень. Така машина передбачає вирішення завдання - або "вдало вгадуючи", або перебираючи все припущення паралельно - і перевіряє своє припущення за поліноміальний час.
ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАНЬ
1. Рощин А.Г., статевих Р.М. Теорія автоматів. Частина I. Тексти лекцій - Москва: МГТУ ГА, 2001. – 76 с.
2. Фалевіч Б.Я. Теорія алгоритмів. - М.: ИНФРА-М, 2006. - 324 с.
3. Фаліна Н.М. Машина Тьюринга // Інформатика. - №26. - 2005. – 126 с.