Машина Тьюринга – це сукупність наступних об'єктів

• 1) зовнішній алфавіт A = (a 0, a 1, …, a n);
• 2) внутрішній алфавіт Q = (q 1, q 2, ..., q m) - безліч станів;
• 3) безліч керуючих символів (П, Л, С)
• 4) нескінченна в обидві сторони стрічка, поділена на комірки, у кожну з яких у будь-який дискретний момент часу може бути записаний лише один символ із алфавіту А;
• 5) керуючий пристрій, здатний перебувати в одному з безлічі станів

Символом порожнього осередку є буква зовнішнього алфавіту а 0 .

Серед станів виділяються початкове q 1 перебуваючи в якому машина починає працювати, і заключне (або стан зупинки) q 0 потрапивши в яке машина зупиняється.

Керуючий пристрій може переміщатися вліво та вправо стрічкою, читати та записувати в комірки стрічки символи алфавіту A. Керуючий пристрій працює згідно з командами, які мають наступний вигляд

q i a j > a p X q k

Запис означає наступне: якщо керуючий пристрій знаходиться в стані q i , а в комірці, що оглядається записана буква a j , то (1) в комірку замість a j записується a p , (2) машина переходить до огляду наступної правої комірки від тієї, яка оглядалася тільки що, якщо Х= П, або до огляду наступної лівої комірки, якщо Х= Л, або ж продовжує оглядати ту саму комірку стрічки, якщо Х= С, (3) керуючий пристрій переходить у стан q k.

Оскільки робота машини, за умовою, повністю визначається її станом q, в даний момент і вмістом комірки, що оглядається в цей момент, то для кожної можливої ​​конфігурації q i a j є рівно одне правило. Правил немає лише для заключного стану, потрапивши до якого машина зупиняється. Тому програма машини Тьюринга із зовнішнім алфавітом A=(a0, a1, …, an) і внутрішнім Q=(q1, q2,…, qm) містить трохи більше m (n+ 1) команд.

Словом в алфавіті А або в алфавіті Q або в алфавіті A Q називається будь-яка послідовність літер відповідного алфавіту. Під k-ою конфігурацією розумітимемо зображення стрічки машини з інформацією, що склалася на ній до початку k-того кроку (або слово в алфавіті А, записане на стрічку до початку k-того кроку), із зазначенням того, який осередок оглядається в цей крок та в якому стані знаходиться машина. Мають сенс лише кінцеві зміни, тобто. такі, в яких всі осередки стрічки, за винятком, можливо, кінцевого числа, порожні. Конфігурація називається завершальною, якщо стан, в якому при цьому знаходиться машина, завершальний.

Якщо вибрати будь-яку незаключну конфігурацію машини Т'юрінга як вихідну, то робота машини полягатиме в тому, щоб послідовно (крок за кроком) перетворювати вихідну конфігурацію відповідно до програми машини доти, доки не буде досягнуто заключної конфігурації. Після цього робота машини Тьюринга вважається закінченою, а результатом роботи вважається досягнута заключна конфігурація.

Будемо говорити, що непусте слово б в алфавіті А (а 0 ) = (a 1 , …, a n ) сприймається машиною в стандартному положенні, якщо воно записано в послідовних осередках стрічки, всі інші осередки порожні, і машина оглядає крайню ліворуч або крайню справа осередок із тих, у яких записано слово б. Стандартне положення називається початковим (заключним), якщо машина, яка сприймає слово у стандартному положенні, знаходиться у початковому стані q 1 (відповідно у стані зупинки q 0).

Якщо обробка слова б переводить машину Тьюринга в заключний стан, то кажуть, що вона може бути застосована до б, інакше - не застосовна до б (машина працює нескінченно)

Розглянемо приклад:

Дана машина Тьюринга із зовнішнім алфавітом А = (0, 1) (тут 0 - символ порожнього осередку), алфавітом внутрішніх станів Q = (q 0 , q 1 , q 2 ) і з наступною функціональною схемою (програмою):

q 1 0 > 1 Л q 2;

q 1 1 > 0 q 2 ;

q 2 0 > 0 П q 0;

q 2 1 > 1 q 1 ;

Цю програму можна записати за допомогою таблиці

На першому кроці діє команда: q 1 0 > 1 Л q 2 (керівник знаходиться в стані q1, а в комірці, що оглядається записана буква 0, в комірку замість 0 записується 1, головка зрушується вліво, керуючий пристрій переходить в стан q2), в результаті на машині створюється наступна конфігурація:

Нарешті після виконання команди q 2 0 > 0 П q 0 створюється конфігурація

Ця конфігурація є заключною, тому що машина опинилася в стані зупинки q0.

Таким чином, вихідне слово 110 перероблено машиною на слово 101.

Отриману послідовність конфігурацій можна записати більш коротким способом (вміст комірки, що оглядається, записано праворуч від стану, в якому знаходиться в даний момент машина):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Машина Тьюринга - нічим іншим, як правило (алгоритм) перетворення слів алфавіту A Q, тобто. конфігурацій. Таким чином, для визначення машини Тьюринга потрібно задати її зовнішній та внутрішній алфавіти, програму та вказати, які із символів позначають порожню комірку та заключний стан.

Машина Тьюринга - одне з найцікавіших і захоплюючих інтелектуальних відкриттів 20-го століття. Це проста та корисна абстрактна модель обчислень (комп'ютерних та цифрових), яка є достатньо загальною для втілення будь-якого комп'ютерного завдання. Завдяки простому описута проведення математичного аналізу вона утворює фундамент теоретичної інформатики. Це дослідження призвело до більш глибокого пізнання цифрових комп'ютерів та обчислень, включаючи розуміння того, що існують деякі обчислювальні проблеми, які не вирішуються на загальних користувальницьких ЕОМ.

Що це та хто створив

Алан Т'юрінг прагнув описати найбільш примітивну модель механічного пристрою, яка мала б ті самі основні можливості, що й комп'ютер. Т'юрінг вперше описав машину в 1936 році в статті "Про обчислювані числа з додатком до проблеми розв'язності", яка з'явилася в Працях Лондонського математичного товариства.

Машина Тьюринга є обчислювальним пристроєм, що складається з головки читання/запису (або сканера) з паперовою стрічкою, що проходить через нього. Стрічка розділена на квадрати, кожен із яких несе одиночний символ - "0" або "1". Призначення механізму у тому, що він виступає як засіб входу і виходу, як і робоча пам'ять зберігання результатів проміжних етапів обчислень.

З чого складається пристрій

Кожна така машина складається із двох складових:

1. Необмежена стрічка. Вона є нескінченною в обидві сторони та поділена на комірки.
2. Автомат – керована програма, головка-сканер для зчитування та запису даних. Вона може бути в кожний момент в одному з безлічі станів.

Кожна машина пов'язує два кінцеві ряди даних: алфавіт вхідних символів A = (a0, a1, ..., am) та алфавіт станів Q = (q0, q1, ..., qp). Стан q0 називають пасивним. Вважається, що пристрій закінчує роботу, коли потрапляє саме на нього. Стан q1 називають початковим - машина починає свої обчислення, перебуваючи на старті у ньому. Вхідне слово розміщується на стрічці по одній літері поспіль у кожній позиції. З обох боків від нього розташовуються лише порожні осередки.

Як працює механізм

Машина Тьюринга має важливу відмінність від обчислювальних пристроїв - її запам'ятовуючий пристрій має нескінченну стрічку, тоді як в цифрових апаратів такий пристрій має смугу певної довжини. Кожен клас завдань вирішує лише одна побудована машина Т'юрінга. Завдання іншого виду передбачають написання нового алгоритму.

Керуючий пристрій, перебуваючи в одному стані, може пересуватися у будь-який бік стрічкою. Воно записує до осередків і зчитує з них символи кінцевого алфавіту. У процесі переміщення виділяється порожній елемент, який заповнює позиції, що не містять вхідних даних. Алгоритм для машини Т'юрінга визначає правила переходу для керуючого пристрою. Вони задають головці запису-читання такі параметри: запис у комірку нового символу, перехід у новий стан, переміщення вліво чи вправо стрічкою.

Властивості механізму

Машина Тьюринга, як та інші обчислювальні системи, має властиві їй особливості, і вони подібні до властивостей алгоритмів:

1. Дискретність. Цифрова машина переходить до наступного кроку n+1 тільки після виконання попереднього. Кожен виконаний етап призначає яким буде n+1.
2. Зрозумілість. Пристрій виконує лише одну дію для одного ж осередку. Воно вписує символ з алфавіту і робить один рух: ліворуч чи праворуч.
3. Детермінованість. Кожній позиції механізмі відповідає єдиний варіант виконання заданої схеми, і кожному етапі дії і послідовність їх виконання однозначні.
4. Результативність. Точний результат кожного етапу визначає машина Тьюринга. Програма виконує алгоритм і за кінцеве число кроків перетворюється на стан q0.
5. Масовість. Кожен пристрій визначено над допустимими словами, що входять до алфавіту.

Функції машини Тюрінга

У вирішенні алгоритмів часто потрібна реалізація функції. Залежно від можливості написання ланцюжка для обчислення, функцію називають алгоритмічно розв'язною або нерозв'язною. Як безліч натуральних чи раціональних чисел, слів у кінцевому алфавіті N для машини розглядається послідовність безлічі - слова у межах двійкового кодового алфавіту В=(0.1). Також результат обчислення враховується «невизначене» значення, що виникає при «зависанні» алгоритму. Для реалізації функції важлива наявність формальної мови в кінцевому алфавіті та розв'язуваність завдання розпізнавання коректних описів.

Програма для пристрою

Програми механізму Тьюринга оформляються таблицями, у яких перші рядок і стовпець містять символи зовнішнього алфавіту і значення можливих внутрішніх станів автомата - внутрішній алфавіт. Табличні дані є командами, що їх сприймає машина Тьюринга. Розв'язання задач відбувається таким чином: літера, яка зчитується головкою в комірці, над якою вона в даний момент знаходиться, і внутрішній стан головки автомата обумовлюють, яку з команд необхідно виконувати. Саме така команда перебуває на перетині символів зовнішнього алфавіту і внутрішнього, що у таблиці.

складники для обчислень

Щоб побудувати машину Тьюринга для вирішення однієї певної задачі, необхідно визначити наступні параметри.

Зовнішній алфавіт. Це деяке кінцеве безліч символів, що позначаються знаком А, складові якого називаються буквами. Один з них – а0 – має бути порожнім. Наприклад, алфавіт пристрою Тьюринга, працюючого з двійковими числами, має такий вигляд: A = (0, 1, а0).

Безперервний ланцюжок букв-символів, що записується на стрічку, називається словом.

Автоматом називається пристрій, який працює без втручання людей. У машині Тьюринга він має для розв'язання завдань кілька різних станів і за умов, що виникають, переміщається з одного положення в інше. Сукупність таких станів каретки є внутрішнім абеткою. Він має буквене позначеннявиду Q = (q1, q2 ...). Одне з таких положень – q1 – має бути початковим, тобто тим, що запускає програму. Ще одним необхідним елементом є стан q0, який є кінцевим, тобто тим, що завершує програму та переводить пристрій у позицію зупинки.

Таблиця переходів. Ця складова є алгоритмом поведінки каретки пристрою в залежності від того, які в даний момент стан автомата і значення символу, що зчитується.

Алгоритм для автомата

Кареткою пристрою Тьюринга під час роботи керує програма, яка під час кожного кроку виконує послідовність наступних дій:

1. Запис символу зовнішнього алфавіту на позицію, зокрема і порожнього, здійснюючи заміну що у ній, зокрема і порожнього, елемента.
2. Переміщення на один крок-комірку вліво або вправо.
3. Зміна власного внутрішнього стану.

Таким чином, при написанні програм для кожної пари символів або положень необхідно точно описати три параметри: a i - елемент з вибраного алфавіту A, напрямок зсуву каретки ("←" вліво, "→" вправо, "точка" - відсутність переміщення) і q k - новий стан пристрою. Наприклад, команда 1 "←" q 2 має значення "замістити символ на 1, зрушити головку каретки вліво на один крок-комірку і зробити перехід у стан q 2 ".

Машина Т'юрінга: приклади

приклад 1.Дана задача побудувати алгоритм, який додає одиницю до останньої цифри заданого числа, розташованого на стрічці. Вхідні дані – слово – цифри цілого десяткового числа, записані у послідовні осередки на стрічку. У початковий момент пристрій розташовується навпроти правого символу - цифри числа.

Рішення. Якщо остання цифра дорівнює 9, то її потрібно замінити на 0 і потім додати одиницю до попереднього символу. Програма в цьому випадку для цього пристрою Тьюринга може бути написана так:

Тут q1 – стан зміни цифри, q0 – зупинка. Якщо в q 1 автомат фіксує елемент з ряду 0..8, він заміщає її на один з 1..9 відповідно і потім перемикається в стан q 0 , тобто пристрій зупиняється. Якщо ж каретка фіксує число 9, то заміщає її на 0, потім переміщається вліво, зупиняючись у стані q 1 . Такий рух триває до того моменту, поки пристрій не зафіксує цифру, меншу за 9. Якщо всі символи виявилися рівними 9, вони заміщаються нулями, на місці старшого елемента запишеться 0, каретка переміститься вліво і запише 1 у порожню клітку. Наступним кроком буде перехід у стан q 0 – зупинка.

приклад 2.Даний ряд символів, що позначають дужки, що відкривають і закривають. Потрібно побудувати пристрій Тьюринга, яке б видаляло пари взаємних дужок, тобто елементів, розташованих поспіль - “()”. Наприклад, вихідні дані: “) (() (()”, відповідь має бути такою: “) .. ((”. Рішення: механізм, перебуваючи в q 1 , аналізує крайній ліворуч елемент у рядку).

Стан q 1: якщо зустрінуто символ “(”, то здійснити зсув праворуч і перехід у положення q 2 ; якщо визначено “a 0 ”, то зупинка.

Стан q 2: проводиться аналіз дужки "(" на наявність парності, у разі збігу має вийти ")". Якщо елемент парний, зробити повернення каретки вліво і перейти в q 3 .

Стан q 3: видалення спочатку символу “(”, а потім “)” і перейти в q 1 .

Досі нам було зручно посилатися на програмістський досвід, говорячи про алгоритми, програми, інтерпретатори, покрокове виконання і т.д. Це дозволяло нам ігнорувати деталі побудови тих чи інших алгоритмів з приводу того, що читач їх легко відновить (або хоча б повірить все-таки не кожен читач у своєму житті писав інтерпретатор паскаля на паскалі).

Але в деяких випадках цього недостатньо. Нехай, наприклад, ми хочемо довести алгоритмічну нерозв'язність якоїсь задачі, у визначенні якої нічого не йдеться про програми (у цьому розділі, наприклад, ми доведемо нерозв'язність проблеми рівності слів у напівгрупах, заданих утворюючими та співвідношеннями). Це зазвичай робиться так. Ми показуємо, що проблема зупинки зводиться до цього завдання. Для цього ми моделюємо роботу довільного алгоритму в термінах розглянутої задачі (що це означає, буде видно з прикладу, що наводиться нижче). При цьому нам важливо, щоб визначення алгоритму було якомога простіше.

Таким чином, наш план такий. Ми опишемо досить просто визначений клас машин (його можна вибирати по-різному, ми будемо використовувати так звані машини Тьюринга), потім оголосимо, що будь-яка функція, що обчислюється, може бути обчислена на такій машині, а потім покажемо, що питання про зупинку машини Тьюринга можна звести до питання рівності слів у напівгрупі.

Інша причина, чому важливі прості обчислювальні моделі (таких моделей багато різні видимашин Тьюринга, адресні машини і т.п.), пов'язана з теорією складності обчислень, коли нас починає цікавити час виконанняпрограм. Але це питання виходить за межі класичної теорії алгоритмів.

Машини Тьюринга: визначення

Машина Тюрінгамає нескінченну в обидві сторони стрічку, Поділену на квадратики ( осередки). У кожному осередку може бути записаний певний символ з фіксованої (для даної машини) кінцевої множини алфавітомданої машини. Один із символів алфавіту виділений і називається "пробілом" передбачається, що спочатку вся стрічка порожня, тобто заповнена пробілами.

Машина Тьюринга може змінювати вміст стрічки за допомогою спеціальної читаючої та пишучої головки, що рухається вздовж стрічки. У кожний момент головка знаходиться в одному з осередків. Машина Тьюринга отримує від головки інформацію про те, який символ та бачить, і в залежності від цього (і від свого внутрішнього стану) вирішує, що робити, тобто який символ записати в поточному осередку і куди зрушити після цього (ліворуч, праворуч або залишитися) на місці). У цьому також змінюється внутрішній стан машини (ми припускаємо, що машина крім стрічки має кінцеву пам'ять , тобто кінцеве число внутрішніх станів). Ще треба домовитись, з чого ми починаємо і коли закінчуємо роботу.

Таким чином, щоб задати машину Т'юрінга, треба вказати такі об'єкти:

Таблиця переходів влаштована в такий спосіб: кожної пари вказана трійка . Тут зрушення одне з чисел -1 (ліворуч), 0 (на місці) та 1 (направо). Отже, таблиця переходів є функція типу S x A -> S x A x (-1,0,1) , визначена тих парах, у яких стан перестав бути заключним.

Залишається описати поведінку машини Тьюринга. У кожний момент є деяка конфігурація, Що складається з вмісту стрічки (формально кажучи, вміст стрічки є довільне відображення Z -> A ), поточної позиції головки (деяке ціле число) і поточного стану машини (елемент S). Перетворення конфігурації в наступну відбувається за природними правилами: ми дивимося в таблиці, що треба робити для даного стану і для даного символу, тобто з'ясовуємо новий стан машини, змінюємо символ на вказаний і після цього зсуваємо головку вліво, вправо або залишаємо на місці. При цьому, якщо новий стан є одним із останніх, робота машини закінчується. Залишається домовитись, як ми подаємо інформацію на вхід машини та що вважається результатом її роботи. Вважатимемо, що алфавіт машини, крім пробілу, містить символи 0 і 1 (а також, можливо, ще якісь символи). Входом та виходом машини будуть кінцеві послідовності нулів та одиниць (двійкові слова). Вхідне слово записується на порожній стрічці, головка машини ставиться в першу клітинку, машина приводиться в початковий стан і запускається. Якщо машина зупиняється, результатом вважається двійкове слово, яке можна прочитати, починаючи з позиції головки і рухаючись праворуч (поки не з'явиться символ, відмінний від 0 і 1).

Таким чином, будь-яка машина Т'юрінга задає деяку часткову функцію на двійкових словах. Усі такі функції природно назвати обчислюваними на машинах Тьюринга.

Машини Тьюринга: обговорення

Зрозуміло, наше визначення містить багато конкретних деталей, які можна було б змінити. Наприклад, стрічка може бути нескінченною лише в один бік. Можна надати машині дві стрічки. Можна вважати, що машина може або написати новий символ, або зрушити, але не те й інше разом. Можна обмежити алфавіт, вважаючи, скажімо, що в ньому має бути рівно 10 символів. Можна вимагати, щоб наприкінці на стрічці нічого не було, крім результату роботи (інші клітини мають бути порожні). Всі перелічені та інші зміни не змінюють класу обчислюваних на машинах Тьюринга функцій. Звісно, ​​є й нешкідливі зміни. Наприклад, якщо заборонити машині рухатися ліворуч, то це радикально поміняє справу, по суті, стрічка стане марною, оскільки до старих записів вже не можна буде повернутися.

Як зрозуміти, які зміни невинні, а які ні? Очевидно, тут потрібен певний досвід практичного програмування на машинах Тьюринга, хоча б невеликий. Після цього вже можна уявляти можливості машини, не виписуючи програми повністю, а керуючись лише приблизним описом. Як приклад опишемо машину, яка подвоює вхідне слово (виготовляє слово XX, якщо на вході було слово X).

Якщо машина бачить пропуск (вхідне слово порожньо), вона закінчує роботу. Якщо ні, вона запам'ятовує поточний символ і ставить позначку (в алфавіті крім символів 0 і 1 будуть ще "помічені варіанти" і ). Потім вона рухається праворуч до порожньої клітки, після чого пише там копію пам'яті символу. Потім вона рухається ліворуч до позначки; уткнувшись у позначку, відходить назад і запам'ятовує наступний символ і так далі, доки не скопіює все слово .

Маючи деякий досвід, можна за всіма цими фразами бачити конкретні шматки програми для машини Тюрінга. Наприклад, слова "запам'ятовує символ і рухається праворуч" означають, що є дві групи станів, одна для ситуації, коли запам'ятовується нуль, інша коли запам'ятана одиниця, і всередині кожної групи запрограмовано рух праворуч до першої порожньої клітини.

Маючи ще трохи більше досвіду, можна зрозуміти, що в цьому описі є помилка, не передбачений механізм зупинки, коли все слово буде скопійовано, оскільки копії символів нічим не відрізняються від символів вихідного слова. Ясно і те, як помилку виправити треба як копії писати спеціальні символи і , а на останньому етапі всі позначки видалити.

77 . Покажіть, що функція "звернення", що перевертає слово задом наперед, обчислюється машиною Тьюринга.

Інший приклад неформального міркування: пояснимо, чому можна використовувати додаткових символів, крім 0 , 1 і порожнього символу. Нехай є машина з великим алфавітом N символів. Побудуємо нову машину, яка моделюватиме роботу старої, але кожній клітині старої відповідатиме блок із k клітин нової. Розмір блоку (число k) буде фіксований так, щоб усередині блоку можна було б закодувати нулями та одиницями всі символи великого алфавіту. Вихідні символи 0 , 1 і порожній кодуватимемо як 0 , за яким йдуть (k-1) порожніх символів, 1 , за яким йдуть (k-1) порожніх символів, і групу з k порожніх символів. Для початку треба розсунути літери вхідного слова на відстань k , Що можна зробити без додаткових символів (дійшовши до крайньої літери, відсуваємо її, потім дійшовши до наступної, відсуваємо її і крайню і так далі); треба лише розуміти, що можна ідентифікувати кінець слова як позицію, за якою слідує більше k порожніх символів. Зрозуміло, що в цьому процесі ми повинні зберігати в пам'яті певний кінцевий обсяг інформації, тому це можливо. Після цього вже можна моделювати роботу вихідної машини по кроках, і для цього теж досить кінцевої пам'яті (е кінцевого числа станів), так як нам важлива лише невелика околиця головки машини, що моделюється. Зрештою, треба стиснути результат назад.

На закінчення обговорення наведемо обіцяний вище аргумент на користь того, що будь-яка функція обчислювана на машині Тьюринга. Нехай є функція, яку людина вміє обчислювати. При цьому він, природно, повинен використовувати олівець і папір, оскільки кількість інформації, яке він може зберігати "розуміється", обмежено. Вважатимемо, що він пише на окремих аркушах паперу. Крім поточного аркуша, є стос паперу праворуч і стос ліворуч; в будь-яку з них можна покласти поточний лист, завершивши з ним роботу, а з іншого стосу взяти наступний. Людина має олівець і гумку. Оскільки дуже дрібні літери не видно, число чітко помітних станів аркуша звичайно, і можна вважати, що в кожний момент на аркуші записана одна літера з деякого кінцевого (хоч і дуже великого) алфавіту. Людина теж має кінцеву пам'ять, так що її стан є елементом деякої кінцевої множини. При цьому можна скласти деяку таблицю, в якій записано, чим закінчиться його робота над аркушем з цим вмістом, розпочата в даному стані (що буде на аркуші, в якому стані буде людина і з якої пачки буде взято наступний аркуш). Тепер уже видно, що дії людини саме відповідають роботі машини Тьюринга з великим (але кінцевим) алфавітом і великим (але кінцевим) числом внутрішніх станів.

тренажер для вивчення універсального виконавця

Що це таке?

Тренажер «Машина Тьюринга» — це навчальна модель універсального виконавця (абстрактної обчислювальної машини), запропонованого в 1936 А. Тьюрингом для уточнення поняття алгоритму. Відповідно до тези Тьюринга, будь-який алгоритм може бути записаний як програми для машини Тьюринга. Доведено, що машина Тьюринга за своїми можливостями еквівалентна машині Поста та нормальним алгоритмам Маркова.

Машина Тьюринга складається з каретки (зчитує і записує головки) і нескінченної стрічки, розбитої на комірки. Кожна клітинка стрічки може містити символ з деякого алфавіту A = (a 0, a 1, ..., a N). Будь-який алфавіт містить символ пробілу, який позначається як a 0 або Λ. При введенні команд пропуск замінюється знаком підкреслення «_».

Машина Тьюринга – це автомат, який керується таблицею. Рядки в таблиці відповідають символам обраного алфавіту A, а стовпці - станам автомата Q = (q 0, q 1, ..., q M). На початку роботи машина Тьюринга перебуває у стані q1. Стан q 0 це кінцевий стан: потрапивши в нього, автомат закінчує роботу.

У кожній клітині таблиці, що відповідає деякому символу a i і деякому стану q j знаходиться команда, що складається з трьох частин:

1. символ з алфавіту A;
2. напрямок переміщення: > (вправо),
3. новий стан автомата

Новини

1. Фаліна І.М.Тема «Машина Тьюринга» у шкільному курсі інформатики (inf.1september.ru).
2. Майєр Р.В.Машини Поста та Тьюринга (komp-model.narod.ru).
3. Пильщиков В.М., Абрамов В.Г., Виліток А.А., Гаряча І.В.Машина Тьюринга та алгоритми Маркова. Вирішення завдань, М.: МДУ, 2006.
4. Бекман І.М.Комп'ютерні науки. Лекція 7. Алгоритми (profbeckman.narod.ru)
5. Соловйов А.Дискретна математика без формул (lib.rus.ec)
6. Єршов С.С.Елементи теорії алгоритмів, Челябінськ, Видавничий центр ЮУрГУ, 2009.
7. Варпахівський Ф.Л.Елементи теорії алгоритмів, М: Просвітництво, 1970.
8. Верещагін Н.К., Шень О.Обчислювані функції, М: МЦНМО, 1999.

Що з цим робити?

У верхній частині програми знаходиться поле редактора, яке можна ввести умову завдання у вільній формі.

Стрічка переміщається вліво та вправо за допомогою кнопок, розташованих ліворуч та праворуч від неї. Подвійним клацанням по комірці стрічки (або клацанням правою кнопкою миші) можна змінити її вміст.

За допомогою меню Стрічкаможна запам'ятати стан стрічки у внутрішньому буфері та відновити стрічку з буфера.

В полі Алфавітзадаються символи вибраного алфавіту. Пробіл автоматично додається до введених символів.

У таблиці у нижній частині вікна набирається програма. У першому стовпчику записані символи алфавіту, він заповнюється автоматично. У першому рядку перераховуються всі можливі стани. Додати та видалити стовпці таблиці (стану) можна за допомогою кнопок, розташованих над таблицею.

При введенні команди в комірку таблиці спочатку потрібно ввести новий символ, потім напрямок переходу та номер стану. Якщо символ пропущено, він не змінюється за замовчуванням. Якщо номер стану пропущено, стан автомата не змінюється.

Праворуч у полі Коментарможна вводити у довільній формі коментарі до рішення. Найчастіше там пояснюють, що означає кожен стан машини Т'юрінга.

Програма може виконуватися безперервно (F9) або кроками (F8). Команда, яка зараз виконуватиметься, підсвічується зеленим тлом. Швидкість виконання регулюється за допомогою меню Швидкість.

Завдання для машини Т'юрінга можна зберігати у файлах. Зберігається умова завдання, алфавіт, програма, коментарі та початковий стан стрічки. При завантаженні завдання з файлу та збереженні у файлі стан стрічки автоматично записується у буфер.

Якщо ви помітили помилку або у вас є пропозиції, зауваження, скарги, прохання та заяви, пишіть .

Технічні вимоги

Програма працює під управлінням операційних систем лінійки Windowsна будь-яких сучасних комп'ютерах.

Ліцензія

Програма безкоштовна для некомерційного використання. Вихідні тексти програми не розповсюджуються.

Програма поставляється « as is», тобто автор не несе жодної відповідальності за всілякі наслідки її використання, включаючи моральні та матеріальні втрати, виведення обладнання з ладу, фізичні та душевні травми.

При розміщенні програми на інших веб-сайтах посилання на першоджерело є обов'язковим.

1. 1) публікація матеріалів у будь-якій формі, у тому числі розміщення матеріалів на інших веб-сайтах;
2. 2) поширення неповних чи змінених матеріалів;
3. 3) включення матеріалів до збірників на будь-яких носіях інформації;
4. 4) отримання комерційної вигоди від продажу чи іншого використання матеріалів.

Завантаження матеріалів означає, що ви прийняли умови цієї ліцензійної угоди.

завантажити

Після розпакування архіву програма перебуває у працездатному стані та не потребує жодних додаткових установок.

1. Опис машини Тьюринга. 3

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

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

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

3. Машина Тьюринга та алгоритмічно нерозв'язні проблеми. 12

Висновок. 16

Список литературы.. 18

Вступ

Машина Тьюринга – це дуже простий обчислювальний пристрій. Вона складається зі стрічки нескінченної довжини, розділеної на комірки, і головки, яка переміщається вздовж стрічки і здатна читати та записувати символи. Також у машини Тьюринга є така характеристика, як стан, який може виражатися цілим числом від нуля до деякої максимальної величини. Залежно від стану машина Тьюринга може виконати одну з трьох дій: записати символ у комірку, пересунутись на одну комірку вправо або вліво та встановити внутрішній стан.

Обладнання машини Тьюринга надзвичайно просто, проте на ній можна виконати практично будь-яку програму. Для виконання всіх цих дій передбачена спеціальна таблиця правил, в якій прописано, що потрібно робити за різних комбінацій поточних станів і символів, прочитаних зі стрічки.

У 1947 р. Алан Т'юрінг розширив визначення, описавши "універсальну машину Тьюринга". Пізніше для вирішення певних класів завдань було введено її різновид, який дозволяв виконувати не одне завдання, а кілька.

1. Опис машини Тьюринга

Передісторія створення цієї роботи пов'язана з формулюванням Давидом Гільбертом на Міжнародному математичному конгресі в Парижі в 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+7n+12, то обчислювальна складність порядку n2 записується як О(n2).

Тимчасова складність виміряна в такий спосіб залежить від реалізації. Не потрібно знати ні точний час виконання різних інструкцій, ні кількість бітів, які використовуються уявлення різних змінних, і навіть швидкість процесора. Один комп'ютер може бути на 50 відсотків швидше за інший, а у третього шина даних може бути вдвічі ширше, але складність алгоритму, оцінена по прядку величини, не зміниться. Це не шахрайство, при роботі з такими складними алгоритмами, як описані в цій книзі, всім іншим можна знехтувати (з точністю до постійного множника) в порівнянні зі складністю по порядку величини.

Ця нотація дозволяє побачити, як обсяг вхідних даних впливає на вимоги до часу та обсягу пам'яті. Наприклад, якщо Т=О(n), то подвоєння вхідних даних подвоїть час виконання алгоритму. Якщо Т=О(2n), то додавання одного біта до вхідних даних подвоїть виконання алгоритму.

Зазвичай алгоритми класифікуються відповідно до їх часової або просторової складності. Алгоритм називають постійним, якщо його складність залежить від n: 0(1). Алгоритм є лінійним, якщо його тимчасова складність О(n). Алгоритми може бути квадратичними, кубічними тощо. Всі ці алгоритми – поліноміальні, їх складність – О(m), де m – константа. Алгоритми з поліноміальною тимчасовою складністю називаються алгоритмами з поліноміальним часом

Алгоритми, складність яких дорівнює О(tf(n)), де t - константа, більша ніж 1, a f(n) - деяка поліноміальна функція від n, називаються експоненціальними. Підмножина експоненціальних алгоритмів, складність яких дорівнює О(сf(n)), де де - константа, a f(n) зростає швидше, ніж постійна, але повільніше, ніж лінійна функція, називається суперполіноміальним.

В ідеалі, криптограф хотів би стверджувати, що алгоритм, найкращий для злому спроектованого алгоритму шифрування, має експоненційну тимчасову складність. На практиці, найсильніші твердження, які можуть бути зроблені при поточному стані теорії обчислювальної складності, мають форму "всі відомі алгоритми розтину даної криптосистеми мають суперполіноміальну часову складність". Тобто, відомі нам алгоритми розтину мають суперполіноміальну тимчасову складність, але поки неможливо довести, що не може бути відкритий алгоритм розтину з поліноміальною тимчасовою складністю. Розвиток теорії обчислювальної складності можливо колись дозволить створити алгоритми, котрим існування алгоритмів з поліноміальним часом розтину можна виключити з математичної точністю.