Зміст
Введення. 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 відсотків швидше іншого, а у третього шина даних може бути в два рази ширше, але складність алгоритму, оцінена по ...
