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

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

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

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

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

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

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

• 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

Запис означає наступне: якщо керуючий пристрій знаходиться в стані qi, а в оглядається осередку записана буква aj, то (1) в осередок замість aj записується ap, (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, ..., an) сприймається машиною в стандартному положенні, якщо воно записано в послідовних комірках стрічки, всі інші осередки порожні, і машина оглядає крайню зліва або крайню справа осередок з тих, в яких записано слово б. Стандартне положення називається початковим (заключним), якщо машина, яка сприймає слово в стандартному положенні, знаходиться в початковому стані 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 створюється конфігурація

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Щоб побудувати машину Тьюринга для вирішення однієї певної задачі, необхідно визначити для неї такі параметри. Зовнішній алфавіт. Це деякий кінцеве безліч символів, позначаються знаком А, складові елементи якого називаються буквами. Один з них - а0 - повинен бути порожнім. Для прикладу, алфавіт пристрої Тьюринга, що працює з двійковими числами, виглядає так: A = (0, 1, а 0). Безперервний ланцюжок букв-символів, що записується на стрічку, іменується словом. Автоматом називається пристрій, який працює без втручання людей. У машині Тьюринга він має для вирішення завдань кілька різних станів і при виразно виникають умовах переміщається з одного положення в інше. Сукупність таких станів каретки є внутрішній алфавіт. Він має літерне позначення виду Q = (q1, q2 ...). Одне з таких положень - q1 - має бути початковим, тобто тим, що запускає програму. Ще одним необхідним елементом є стан q0, яке є кінцевим, тобто тим, що завершує програму і дає змогу встановити в позицію зупинки.

Таблиця переходів.

Ця складова є алгоритм поведінки каретки пристрою в залежності від того, які в даний момент стан автомата і значення зчитує сімвола.-

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

Кареткою пристрої Тьюринга під час роботи управляє програма, яка під час кожного кроку виконує послідовність наступних дій: Запис символу зовнішнього алфавіту в позицію, в тому числі і порожнього, здійснюючи заміну знаходився в ній, в тому числі і порожнього, елемента. Переміщення на один крок-осередок вліво або ж вправо. Зміна свого внутрішнього стану. Таким чином, при написанні програм для кожної пари символів або положень необхідно точно описати три параметра: ai - елемент з обраного алфавіту A, напрямок зсуву каретки ( "←" вліво, "→" вправо, "точка" - відсутність переміщення) і qk - новий стан пристрою. наприклад, команда 1 "←" q2 має значення "замістити символ на 1, зрушити голівку каретки вліво на один крок-осередок і зробити перехід в стан q2".

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

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

Наприклад, рішення квадратного рівняння:

1. Привести рівняння до канонічної форму \ (a x ^ 2 + b x + c = 0 \)
2. Якщо \ (a = 0 \), то це лінійне рівняння з рішенням \ (x = \ frac (-c) (b) \). Завдання вирішена. Інакше, перейти до кроку 3.
3. Обчислити дискримінант \ (D = b ^ 2-4 a c \)
4. Обчислити рішення рівняння \ (X_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \). Завдання вирішена.

Можна ввести наступне інтуїтивне поняття алгоритму:

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

Це, звичайно, не строге визначення, але воно описує суть поняття алгоритму.

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

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

Виділяються наступні властивості алгоритмів:

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

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

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

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

Крім того, обмежений так само і набір можливих дій виконавця, оскільки якби були допустимі будь-які дії, то серед них мало б бути так само і "неприпустиме".

Суворе визначення алгоритму

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

Виявляється, існує клас алгоритмічно нерозв'язних задач- завдань, для яких неможливо скласти алгоритм рішення. Але щоб строго довести алгоритмічну нерозв'язність, потрібно для початку мати суворе визначення алгоритму.

У 20-30 роках XX століття, над проблемою суворого визначення алгоритму працювали різні математики, зокрема Алан Тьюринг, Еміль Пост, Андрій Андрійович Марков, Андрій Миколайович Колмогоров, Алонзо Черч і інші. Їх робота в підсумку привела до виникнення і розвитку теорії алгоритмів, теорії ісчісліми і різних підходів до обчислення, і, до речі, програмування в цілому. Одним з результатів їх роботи стала поява кількох суворих визначень алгоритму, введених різному, але еквівалентних один одному.

Ми докладно зупинимося на визначенні Тьюринга, і поверхнево розберемо еквівалентні визначення Посту, Черча і Маркова.

машина Тьюринга

Для введення формального визначення алгоритму, Тьюринг придумав і описав абстрактну обчислювальну машину, звану обчислювальною машиною Тьюринга, або просто машиною Тьюринга.

Алан Тьюринг (1912-1954)

Англійський математик, логік, криптограф, можливо перший в світі "хакер", стояв біля витоків інформатики та теорії штучного інтелекту. Вніс істотний внесок в перемогу союзних військ у Другій світовій війні.

В якості вхідних даних для машини Тьюринга використовуються слова, Складені за допомогою якогось алфавіту, Тобто, набору символів.

Результатом роботи машини Тьюринга так само є слова.

Слово, до якого застосовується алгоритм, називається вхідним. Слово, яке виходить в результаті роботи, вихідним.

Набір слів, до яких застосовується алгоритм, називається областю застосовності алгоритму.

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

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

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

Керуючий пристрій може переміщатися вліво і вправо по стрічці, читати і записувати в осередки символи деякого кінцевого алфавіту. Виділяється особливий порожній символ, що позначається \ (a_0 \) або \ (\ Lambda \), що заповнює всі клітини стрічки, крім тих з них (кінцевого числа), на яких записані вхідні дані.

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

Хоча машина Тьюринга є абстрактною концепцією, досить просто уявити собі подібну машину (правда, з кінцевою стрічкою), і навіть існують демонстраційні машини в такому роді:

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

Команда, в свою чергу, може мати наступну структуру:

\ [A_k \ left \ lbrace \ begin (matrix) Л \\ Н \\ П \ end (matrix) \ right \ rbrace q_m \]

Спочатку йде символ алфавіту, який повинен бути записаний в поточну комірку \ (a_k \), потім, вказується переміщення автомата вліво (Л), вправо (П) або нікуди (залишитися на місці, Н). В кінці вказується новий стан, в яке повинен перейти автомат \ (q_m \).

Осередок таблиці, ясно, визначається поточним символом \ (a_i \) і поточним станом автомата \ (q_j \).

Домовимося, що на початку роботи, машина Тьюринга знаходиться в початковому стані, Що позначається \ (q_1 \), а при переході в стан зупинки\ (Q_0 \) робота алгоритму завершена і машина зупиняється.

приклад

Складемо алгоритм для машини Тьюринга, який додасть до вхідному слову, який представляє собою десяткове число, 1.

Тоді, описово, алгоритм можна сформулювати наступним чином:

1. Переміщаючись вправо, знайти початок вхідного слова
2. Переміщаючись вправо, знайти кінець вхідного слова
3. Додати один до поточного розряду вхідного слова. Якщо там цифра від 0 до 8, завершити роботу. Інакше, записати 0, переміститися вліво, і повернутися до кроку 3.

Запишемо цей алгоритм у вигляді таблиці. Алфавіт складається з цифр від 0 до 9 і "порожнього символу" \ (\ Lambda \). Так само нам потрібно 4 стану автомата, вважаючи стан зупинки, відповідних кроків опису алгоритму.

Домовимося, що початковий стан \ (1 \) - пошук початку вхідного слова, \ (2 \) - пошук кінця вхідного слова, \ (3 \) - додаток 1.

\ (_ (Q_j) \ backslash ^ (a_i) \)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛП1	0Н2	1Н2	2Н2	3Н2	4Н2	5Н2	6Н2	7Н2	8Н2	9Н2
2	ΛЛ3	0П2	1П2	2П2	3П2	4П2	5П2	6П2	7П2	8П2	9П2
3	1Н0	1Н0	2Н0	3Н0	4Н0	5Н0	6Н0	7Н0	8Н0	9Н0	0Л3

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

	1	9	9
1

У стані 1, автомат знаходиться над порожньою осередком. Відповідна команда з таблиці "ΛП1", тобто, залишити осередок порожній, переміститися вправо і залишитися в стані 1:

	1	9	9
	1

Тепер автомат спостерігає значення "1". Відповідна команда "1Н2", тобто залишити в осередку "1", перестати висуватися, і перейти в стан "2":

	1	9	9
	2

У стані "2", автомат спостерігає значення "1". Відповідна команда "1П2", тобто залишити "1", переміститися вправо і залишитися в стані "2":

Ситуація повторюється:

Тепер, в стані 3 і спостерігаючи символ "9", автомат виконує команду "0Л3":

	1	9	0
		3

Ситуація повторюється:

Стан "0" - стан зупинки. Робота алгоритму завершена.

формальний опис

Математично, машину Тьюринга можна описати таким чином:

Машина Тюрінга (МТ)

це система виду \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), де

• \ (A \) - кінцеве безліч символів алфавіту МТ
• \ (A_0 \ in A \) - порожній символ алфавіту
• \ (Q \) - кінцеве безліч станів МТ
• \ (Q_1 \ in Q \) - початковий стан МТ
• \ (Q_0 \ in Q \) - кінцевий стан МТ (стан зупинки)
• \ (T = \ (Л, П, Н \) \) - безліч зрушень МТ
• \ (\ Tau \) - програма МТ, тобто функція, що задає відображення \ (\ Tau: A \ times Q \ backslash \ (q_0 \) \ rightarrow A \ times T \ times Q \)

Ключовим в теорії алгоритмів є теза Тьюринга.

У вільній формулюванні, теза Тьюринга формулюється так:

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

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

Альтернативні визначення алгоритму

Крім машини Тьюринга, існує кілька незалежних визначень, еквівалентних визначення Тьюринга.

Зокрема, визначення через машину Посту, через лямбда-числення Черча, нормальний алгоритм Маркова.

Розглянемо ці способи.

машина Поста

Через рік після Тьюринга, американський математик Еміль Пост незалежно запропонував іншу абстрактну універсальну обчислювальну машину, яка є певним спрощенням в порівнянні з машиною Тьюринга.

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

В іншому, машина Посту аналогічна машині Тьюринга: є автомат, і є нескінченна стрічка з осередками.

Машина Поста може виконувати наступні команди:

1. Записати 1, перейти до i-тому рядку програми
2. Записати 0, перейти до i-тому рядку програми
3. Виконати зрушення вліво, перейти до i-тому рядку програми
4. Виконати зрушення вправо, перейти до i-тому рядку програми
5. Умовний перехід: якщо в спостережуваної осередку 0, перейти до i-тому рядку програми, інакше - перейти до j-тому рядку програми.
6. Зупинка.

Так само машина Посту має кілька заборонених команд:

1. Запис в клітинку 1, коли там уже 1.
2. Запис в клітинку 0, коли там уже 0.

Подібні події призводять до аварійного завершення роботи.

Для написання програм для машини поста можна використовувати такі позначення:

1. ∨ i - записати 1, перейти до i-тому рядку програми
2. × i - записати 0, перейти до i-тому рядку програми
3. ← i - виконати зрушення вліво, перейти до i-тому рядку програми
4. → i - виконати зрушення вправо, перейти до i-тому рядку програми
5. ? i; j - умовний перехід: якщо в спостережуваної осередку 0, перейти до i-тому рядку програми, інакше - перейти до j-тому рядку програми.
6. ! - останов.

Приклад програми:

1. → 2 2.? 1; 3 3. × 4 4. ← 5 5.!

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

За великим рахунком, машина Посту є попередником імперативнихмов програмування, наприклад, C, Fortran і ін.

Машина Поста є еквівалентною машині Тьюринга. Іншими словами, для будь-якої програми для машини Тьюринга, можна записати еквівалентну програму для машини Поста, і навпаки.

Одним з важливих наслідків цієї еквівалентності є те, що будь-який алфавіт можна звести до двійкового коду.

Аналогічно тези Тьюрінга, існує так само і теза Посту.

Теза Посту всякий алгоритм представимо у вигляді машини Посту.

Нормальний алгоритм Маркова

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

Визначення будь-якого нормального алгоритму складається з двох частин:

1. алфавітуалгоритму
2. схемиалгоритму

Сам алгоритм застосовується до словами, Тобто послідовностей символів алфавіту.

Схемою нормального алгоритму називається кінцевий впорядкований набір так званих формул підстановки, Кожна з яких може бути простийабо заключній. Простими формулами підстановки називаються вирази вигляду \ (L \ to D \), де \ (L \) і \ (D \) - два довільних слова, складених з алфавіту алгоритму (звані, відповідно, лівою і правою частинами формули підстановки). Аналогічно, заключними формулами підстановки називаються вирази вигляду \ (L \ to \ cdot D \), де \ (L \) і \ (D \) - два довільних слова, складених з алфавіту алгоритму.

При цьому передбачається, що допоміжні символи \ (\ to \) і \ (\ to \ cdot \) не належать алфавітом алгоритму.

Процес застосування нормального алгоритму до довільного слова \ (V \) являє собою наступну послідовність дій:

1. Нехай \ (V "\) - слово, отримане на попередньому кроці роботи алгоритму (або вихідне слово, якщо поточний крок є першим).
2. Якщо серед формул підстановки немає такої, ліва частина якої входила б в \ (V "\), то робота алгоритму вважається завершеною, і результатом цієї роботи вважається слово \ (V" \).
3. Інакше серед формул підстановки, ліва частина яких входить в \ (V "\), вибирається найперша.
4. З усіх можливих уявлень слова \ (V "\) у вигляді \ (RLS \) (де \ (R \) - префікс, а \ (L \) - суфікс) вибирається таке, при якому \ (R \) - найкоротший , після чого виконується підстановка \ (V "= RDS \).
5. Якщо формула підстановки була кінцевою, то алгоритм завершено з результатом \ (V "\). Інакше, перехід до пункту 1 (наступного кроку).

Будь-яка нормальна алгоритм еквівалентний деякої машині Тьюринга, і навпаки - будь-яка машина Тьюринга еквівалентна певного нормальному алгоритму.

Аналог тези Тьюрінга для нормальних алгоритмів прийнято називати принципом нормалізації.

приклад

Даний алгоритм перетворює двійкові числа в "одиничні" (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.

Алфавіт: (0, 1, |) Правила:

1. 1 → 0|
2. |0 → 0||
3. 0 → (порожній рядок)

Вихідна рядок: 101 Виконання:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

рекурсивні функції

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

• примітивно рекурсивні функції
• общерекурсівние функції
• частково рекурсивні функції

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

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

Примітивно рекурсивні функції

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

До базових функцій відносяться:

• Нульова функція \ (O () = 0 \) - функція без аргументів, яка завжди повертає \ (0 \).
• Функція проходження \ (S (x) = x + 1 \) - функція, яка будь-якому натуральному числу \ (x \) ставить у відповідність наступне число \ (x + 1 \)
• функції \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), Де \ (0

Для конструювання інших функцій класу використовуються оператори:

• Підстановки. Для функції \ (f \) від \ (m \) змінних і \ (m \) функцій \ (g_1, \ ldots, g_m \) від \ (n \) змінних кожна, результатом підстановки \ (g_k \) в \ ( f \) є функція \ (H (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \)від \ (n \) змінних.
• Примітивної рекурсії. Нехай \ (f (x_1, \ ldots, x_n) \) - функція від \ (n \) змінних, а \ (g (x_1, \ ldots, x_ (n + 2)) \) - функція від \ (n + 2 \) змінних. Тоді результатом застосування оператора примітивної рекурсії до функцій \ (f \) і \ (g \) є функція \ (h \) від \ (n + 1 \) змінної виду: \ [H (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [H (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Частково рекурсивні функції

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

Оператор мінімізації аргументу

Нехай \ (f \) - функція від \ (n \) змінних \ (x_i \ in \ mathbb (N) \). Тоді результатом застосування оператора мінімізації аргументу до функції \ (f \) є функція \ (h \) від \ (n-1 \) аргументу, що визначається як:

\ [H (x_1, \ ldots, x_ (n-1)) = \ min y, \]де \ Тобто, \ (h \) повертає мінімальне значення останнього аргументу функції \ (f \) при якому значення \ (f \) дорівнює нулю.

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

Більш строго частково рекурсивні функції слід було б називати "частково певні рекурсивні функції", оскільки вони визначені тільки на частині можливих значень аргументів.

Общерекурсівние функції

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

Теорія обчислюваності і проблема зупинки

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

Дослідженням таких завдань займається теорія обчислюваності.

Прикладами алгоритмічно нерозв'язних завдань є проблема зупинкиі проблема розпізнавання виводимості. Розглянемо їх більш детально.

Проблема зупинки За описом алгоритму A і вхідних даних \ (x \) необхідно з'ясувати, чи зупиниться алгоритм \ (A \) на вхідних даних \ (x \).

Проблема зупинки є алгоритмічно нерозв'язною. Доведемо це.

\ (\ Delta \)

Нехай існує універсальний алгоритм, що вирішує проблему зупинки. Розглянемо тоді клас алгоритмів, що обробляє тексти опису алгоритмів.

В силу існування універсального алгоритму вирішення проблеми зупинки, існує алгоритм, який визначає, чи зупиниться алгоритм зі згаданого класу на власному тексті, чи ні. Позначимо такий алгоритм \ (B \).

Побудуємо алгоритм \ (C \), вхідними даними для якого є текст алгоритму \ (A \), який займається обробкою свій текст:

1. Виконати алгоритм \ (B \) над \ (A \).
2. Якщо алгоритм \ (B \) визначив, що \ (A \) зупиниться на своєму тексті, перейти до кроку 1. Інакше - до кроку 3.
3. Кінець алгоритму \ (C \).

Спробувавши застосувати алгоритм \ (C \) до алгоритму \ (C \), прийдемо до очевидного протиріччя: якщо \ (C \) зупиниться на власному тексті, то він не може зупинитися, і навпаки. Отже, не існує алгоритму \ (B \). \ (\ Not \ Delta \)

Більш загальним формулюванням проблеми зупинки є проблема визначення виводимості.

Проблема розпізнавання виводимості

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

Чи існує для будь-яких двох слів \ (R \) і \ (S \) дедуктивна ланцюжок, що веде від \ (R \) до \ (S \) в рамках даного логічного обчислення?

У 1936 році Алонзо Черч довів теорему Черча.

Теорема Черча Проблема розпізнавання виводимості алгоритмічно нерозв'язна.

Черч використовував для доказу формалізм лямбда-числення. У 1937 незалежно від нього ту ж теорему довів Тьюринг, використовуючи формалізм машини Тьюринга.

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

Обчислювана функція функція, для обчислення якої можна скласти алгоритм.

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

Приклад невичіслімой функції

Візьмемо функцію \ (h (n) \), певну для \ (\ forall n \ in \ mathbb (N) \) наступним чином:

\ [H (n) = \ begin (cases) 1, & \ text (якщо в) \ pi \ text (є послідовність з рівно) n \ text (9-к) \\ 0, & \ text (в іншому випадку ) \ end (cases) \]

Ми можемо отримати значення \ (1 \) для цієї функції, однак, щоб отримати значення \ (0 \), потрібно перевірити нескінченне десяткове розкладання числа \ (\ pi \), що, очевидно, неможливо за кінцевий час. Ця функція, таким чином, є невичіслімой.

Після 1920-х років вираз обчислювальна машинавідносять до будь-яких машин, які виконували роботу людини-комп'ютера, Особливо до тих, які були розроблені відповідно до ефективними методами тези Черча - Тьюринга. Ця теза формулюється як: «Всякий алгоритм може бути заданий у вигляді відповідної машини Тьюринга або частково рекурсивного визначення, а клас обчислюваних функцій збігається з класом частково рекурсивних функцій і з класом функцій, обчислюваних на машинах Тьюрінга». По-іншому, теза Черча-Тьюринга визначається як гіпотеза про природу механічних пристроїв розрахунків, таких як електронно-обчислювальні машини. Будь-яке обчислення, яке тільки можливо, може бути виконано на комп'ютері, за умови, що в ньому досить часу і місця для зберігання.

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

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

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

Машини Тьюринга були розроблені, щоб формально математично визначити, що може бути обчислено з урахуванням обмежень на обчислювальну здатність. Якщо машина Тьюринга може виконати завдання, то завдання вважається обчислюваною по Тьюрингу. Тьюринг в основному зосередився на проектуванні машини, яка могла визначити, що може бути обчислено. Тьюринг зробив висновок, що, поки існує машина Тьюринга, яка могла б обчислювати наближення числа, це значення ісчісліми. Крім того, машина Тьюринга може інтерпретувати логічні оператори, такі як AND, OR, XOR, NOT, і «Якщо-Те-Иначе», щоб визначити, чи є