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

Зміст

Введення. 2
1. Опис машини Тьюрінга. 3
1.1 Властивості машини Тьюринга як алгоритму. 5
2. Складність алгоритмів. 7
2.1 Складність проблем .. 9
3. Машина Тьюринга і алгоритмічно нерозв'язні проблеми .. 12
Висновок. 16
Список літератури .. 18

Введення

Машина Тьюрінга - це дуже просте обчислювальний пристрій. Вона складається з стрічки нескінченної довжини, поділеної на клітинки, і головки, яка переміщається уздовж стрічки і здатна читати і записувати символи. Також у машини Тьюринга є така характеристика, як стан, що може виражатися цілим числом від нуля до деякої максимальної величини. Залежно від стану машина Тьюрінга може виконати одну з трьох дій: записати символ в комірку, пересунутися на одну клітинку вправо або вліво і встановити внутрішній стан.
Будова машини Тьюрінга надзвичайно просто, проте на ній можна виконати практично будь-яку програму. Для виконання всіх цих дій передбачена спеціальна таблиця правил, у якій прописано, що потрібно робити при різних комбінаціях поточних станів і символів, прочитаних зі стрічки.
У 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) функція переходу не визначена.
Алан Тьюринг висловив припущення, що будь-який алгоритм в інтуїтивному розумінні цього слова може бути представлений еквівалентної машиною Тьюрінга. Це припущення відомо як теза Черча-Тюринга. Кожен комп'ютер може моделювати машину Тьюрінга (операції перезапису осередків, порівняння і переходу до іншої сусідньої осередку з урахуванням зміни стану машини). Отже, він може моделювати алгоритми в будь-якому формалізмі, і з цієї тези випливає, що всі комп'ютери (незалежно від потужності, архітектури і т.д.) еквівалентні з точки зору принципової можливості вирішення алгоритмічних задач.

1.1 Властивості машини Тьюринга як алгоритму

На прикладі машини Тьюрінга добре простежуються властивості алгоритмів. Попросіть учнів показати, що машина Тьюрінга має всі властивості алгоритму.
Дискретність. Машина Тьюрінга може перейти до (до + 1) - му кроці тільки після виконання кожного кроку, т.к саме кожен крок визначає, яким буде (до + 1) - й крок.
Зрозумілість. На кожному кроці в клітинку пишеться символ з алфавіту, автомат робить один рух (Л, П, Н), і машина Тьюрінга переходить в одне з описаних станів.
Детермінованість. У кожній клітці таблиці машини Тьюрінга записаний лише один варіант дії. На кожному кроці результат визначений однозначно, отже, послідовність кроків вирішення завдання визначена однозначно, тобто якщо машині Тьюрінга на вхід подають одне і те ж вхідне слово, то вихідний слово кожен раз буде одним і тим же.
Результативність. Змістовно результати кожного кроку і всієї послідовності кроків визначені однозначно, отже, правильно написана машина Тьюринга за кінцеве число кроків перейде в стан q0, тобто за кінцеве число кроків буде отримана відповідь на питання завдання.
Масовість. Кожна машина Тьюрінга визначена над всіма допустимими словами з алфавіту, в цьому і полягає властивість масовості. Кожна машина Тьюрінга призначена для рішення одного класу задач, тобто для кожного завдання пишеться своя (нова) машина Тьюрінга.

2. Складність алгоритмів

Складність алгоритму визначається обчислювальними потужностями, необхідними для його виконання. Обчислювальна складність алгоритму часто вимірюється двома параметрами: Т (тимчасова складність) і S (просторова складність, або вимоги до пам'яті). І Т, і S зазвичай подаються у вигляді функцій від n, де n - це розмір вхідних даних. (Існую і інші способи вимірювання складності: кількість випадкових біт, ширина каналу зв'язку, обсяг даних, і т.п.)
Зазвичай обчислювальна складність алгоритму виражається за допомогою нотації "Про великого", тобто описується порядком величини обчислювальної складності. Це просто член розкладання функції складності, швидше за все зростаючий із зростанням n, всі члени нижчого порядку ігноруються. Наприклад, якщо тимчасова складність даного алгоритму дорівнює 4n2 +7 n +12, то обчислювальна складність порядку n2, що записується як О (n2).
Тимчасова складність виміряна таким чином не залежить від реалізації. Не потрібно знати ні точний час виконання різних інструкцій, ні число бітів, використовуваних для представлення різних змінних, ні навіть швидкість процесора. Один комп'ютер може бути на 50 відсотків швидше за інше, а у третього шина даних може бути в два рази ширше, але складність алгоритму, оцінена за прядку величини, не зміниться. Це не шахрайство, при роботі з алгоритмами настільки складними, як описані в цій книзі, всім іншим можна нехтувати (з точністю до постійного множника) в порівнянні зі складністю по порядку величини.
Ця нотація дозволяє побачити, як обсяг вхідних даних впливає на вимоги до часу і обсягу пам'яті. Наприклад, якщо Т = О (n), то подвоєння вхідних даних подвоїть і час виконання алгоритму. Якщо Т = О (2n), то додавання одного біта до вхідних даних подвоїть час виконання алгоритму.
Зазвичай алгоритми класифікуються відповідно до їх часової чи просторової складністю. Алгоритм називають постійним, якщо його складність не залежить від n: 0 (1). Алгоритм є лінійним, якщо його часова складність О (n). Алгоритми можуть бути квадратичними, кубічними і т.д. Всі ці алгоритми - поліноміальних, їх складність - О (m), де m - константа. Алгоритми з поліноміальної тимчасової складністю називаються алгоритмами з поліноміальним часом
Алгоритми, складність яких дорівнює О (tf (n)), де t - константа, більша, ніж 1, af (n) - деяка поліноміальна функція від n, називаються експоненціальними. Підмножина експоненційних алгоритмів, складність яких дорівнює О (СF (n)), де де с - константа, af (n) зростає швидше, ніж постійна, але повільніше, ніж лінійна функція, називається суперполіноміальним.
В ідеалі, криптограф хотів би стверджувати, що алгоритм, кращий для злому спроектованого алгоритму шифрування, володіє експоненційної тимчасової складністю. На практиці, найсильніші твердження, які можуть бути зроблені при поточному стані теорії обчислювальної складності, мають форму "всі відомі алгоритми розтину даної криптосистеми володіють суперполіноміальной тимчасової складністю". Тобто, відомі нам алгоритми розтину мають суперполіноміальной тимчасової складністю, але поки що неможливо довести, що не може бути відкритий алгоритм розкриття з поліноміальної тимчасової складністю. Розвиток теорії обчислювальної складності можливо коли-небудь дозволить створити алгоритми, для яких існування алгоритмів з поліноміальним часом розтину може бути виключено з математичною точністю.
Зі зростанням n часова складність алгоритмів може стати настільки величезною, що це вплине на практичну реалізованість алгоритму.
За умови, що одиницею часу для нашого комп'ютера є мікросекунд, комп'ютер може виконати постійний алгоритм за мікросекунду, лінійний - за секунду, а квадратичний - за 11.6 дня. Виконання кубічного алгоритму зажадає 32 тисяч років, що в принципі реалізоване, комп'ютер, конструкція якого дозволила б йому протистояти наступного льодовикового періоду, врешті-решт отримав би рішення. Виконання експоненціального алгоритму марно, незалежно від екстраполяції зростання могутності комп'ютерів, паралельної обробки або контактів з інопланетним суперразумом.
Погляньмо на проблему розтину алгоритму шифрування грубою силою. Тимчасова складність такого розтину пропорційна кількості можливих ключів, яке експоненціально залежить від довжини ключа. Якщо n - довжина ключа, то складність розкриття грубою силою дорівнює 0 (2n). Складність розкриття грубою силою при 56-бітовому ключі становить 256, а при 112-бітовому ключі - 2112. У першому випадку розтин можливо, а в другому - ні.

2.1 Складність проблем

Теорія складності також класифікує і складність самих проблем, а не тільки складність конкретних алгоритмів вирішення проблеми. Теорія розглядає мінімальний час і обсяг пам'яті, необхідні для вирішення найважчого варіанту проблеми на теоретичному комп'ютері, відомому як машина Тьюрінга. Машина Тьюринга являє собою кінцевий автомат з нескінченною стрічкою пам'яті для читання запису і є реалістичною моделлю обчислень.
Проблеми, які можна вирішити за допомогою алгоритмів з поліноміальним часом, називаються розв'язуваними, тому що для розумних вхідних даних зазвичай можуть бути вирішені за розумний час. (Точне визначення "розумності" залежить від конкретних обставин) Проблеми, які неможливо вирішити за поліноміальний час, називаються нерозв'язним, тому що обчислення їх рішень швидко стає неможливим. Нерозв'язані проблеми іноді називають важкими. Проблеми, які можуть бути вирішені лише за допомогою суперполіноміальних алгоритмів, обчислювально не вирішується, навіть при відносно малих значеннях n.
Що ще гірше, Алан Тьюринг довів, що деякі проблеми принципово неможливо розв'язати. Навіть відволікаючись від часової складності алгоритму, неможливо створити алгоритм вирішення цих проблем.
Завдання можна розбити на класи відповідно до складності їх вирішення. Ось найважливіші з них і передбачувані співвідношення між ними:
P <= NP <= EXPTIME
Знаходиться зліва клас P включає всі завдання, які можна вирішити за поліноміальний час. В клас NP входять всі завдання, які можна вирішити за поліноміальний час тільки на недетермінованої машині Тьюрінга (це варіант звичайної машини Тьюринга, яка може робити припущення). Така машина передбачає рішення задачі - або "вдало вгадуючи", або перебираючи всі припущення паралельно - і перевіряє своє припущення за поліноміальний час.
Клас NP включає в себе клас P, оскільки будь-яке завдання, вирішуване за поліноміальний час на детермінованої (звичайної) машині Тьюринга, можна вирішити і на недетермінованої за поліноміальний час, просто етап припущення опускається.
Якщо всі завдання класу NP вирішуються за поліноміальний час і на детермінованою машині, то P = NP. Тим не менш, ніким не доведено, що P <> NP (або P = NP). Однак, більшість фахівців, що займаються теорією складності, переконані, що це класи нерівні.
Як не дивно, можна довести, що деякі NP-задачі настільки ж важкі, що й будь-яке завдання цього класу. Такі завдання називаються NP-повними. Тобто, якщо таке завдання вирішується за поліноміальний час, то P = NP.
Таким чином, для програміста NP-повнота означає повний перебір, причому складність цього перебору буде експоненційної або факторіальною. Але слід розуміти, що не всякий повний перебір має таку складність. Наприклад, якщо вирішувати завдання з попереднього випуску повним перебором, то складність отриманих алгоритмів буде поліноміальної - O (n2) для задачі про підпослідовності і O (n6) для задачі про підматриці.
Нарешті, існує клас завдань EXPTIME. Ці завдання вирішуються за експоненційний час. В даний час можна довести, що EXPTIME-повні задачі неможливо вирішити за детерміноване поліноміальний час. Крім того, доведено, що P <> EXPTIME.

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. - С.12-15