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

Лекція 13.Машіна Тьюринга. Обчислюваних (рекурсивні) функції. Універсальні рекурсивні функції.

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

Нагадаємо, що часткової функцією називається "функція"

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

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

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

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

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

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

Машиною Тьюринга називається часткове відображення

тут

позначає "ліво", "право". Той факт, що відображення

часткове, означає, що

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

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

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

А саме, есліто в разі, коли машина знаходиться в стані

а на оглядається в даний момент осередку написаний символ

машина повинна записати в цей осередок

замість

перейти в стан

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

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

Якщо ж

не визначене, то машина, перебуваючи в стані

і оглядаючи осередок з символом

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

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

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

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

номера станів,

напрямок руху, а

символи на стрічці, запишемо рядок

і назвемо еёкомандой. Сукупність усіх команд - це і є програма. якщо

не визначене, то в програмі немає жодної команди, що починається з

Крім того, для будь-яких

в програмі є не більше однієї команди, що починається з

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

Алгоритм дій можна записати словами:

1-й крок: пройти перший масив одиниць, знайти масив з нулів, що йде після нього і замінити перший нуль одиницею;

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

3-й крок: пройти другий масив одиниць і зупинитися в його кінці.

Машина Тьюринга, яка реалізує цей алгоритм, має наступну програму:

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

Будемо називати в цьому розділі натуральними числами цілі невід'ємні числа, тобто дозволимо числу 0 називатися натуральним числом. Таким чином, N безліч натуральних чисел. Як на стрічці позначити натуральне число