Існування універсальних обчислювачів

Існування універсальних вичіслітелей.Алгорітміческіе проблеми і взаємозв'язок алгоритмічних систем.

Існування універсальних обчислювачів.

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

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

Отже, нехай нам треба побудувати Універсальну Машину Тьюринга, назвемо її УМТ, для якої:

вихідними даними є програма іншої машини, назвемо її МТ, з вихідними даними Д останньої;

результат застосування УМТ до цих вихідних даних повинен бути таким же, як застосування МТ до її вихідними даними, тобто

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

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

Інтерпретує алгоритм для УМТ:

Оглядає, осередком, під якою написана буква (стан);

Відшукай в таблиці рядок, позначену цією буквою;

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

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

Якщо другий буквою трійки є "!", То стоп;

Якщо в оглядається осередку третя буква "Н", то зітри букву під оглядає, осередком і запиши туди другу літеру трійки (зміна стану);

Якщо в оглядається трійці третя буква "Л", то зітри букву під оглядає, осередком, зрушимо вліво і запиши під цією осередком другу літеру трійки;

Якщо в оглядається трійці третя буква "П", то зітри букву під оглядає, осередком, зрушимо вправо і запиши під цією осередком другу літеру трійки;

Перейди до кроку 1.

Для того, щоб перетворити це опис в програму Машини Тюрінга, треба вирішити дві основні проблеми:

Як задавати програму і конфігурацію імітованої МТ на стрічці?

Так як довільна МТ може мати довільний алфавіт, то який алфавіт повинен бути у УМТ?

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

як задати програму на стрічці?

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

Програму МТ будемо записувати п'ятірками

aqbp *, де a, bÎD; p, qÎQ; *Î,

тут a- символ. відповідний рядку таблиці;

q - колонки таблиці.

На малюнку 4.1. показана лінійна запис функціональної схеми для U1 (n).

Мал. 4.1. Лінійна запис функціональної схеми МТ, що обчислює U1 (n).

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

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

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

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

один і той же символ з алфавіту МТ завжди зображувався однієї і тієї ж послідовністю символів з алфавіту УМТ;

різні символи з алфавіту МТ завжди зображувалися різними послідовностями символів з алфавіту УМТ.

Як алфавіту УМТ виберемо алфавіт, розширений невеликою кількістю допоміжних символів. Нехай нам треба закодувати символи МТ, у якій | DМТ | = k; | QМТ | = m.

Візьмемо 3 + k + m слів виду 1000 ...... 01, тобто послідовність нулів між одиницями. Ці слова ми будемо називати кодовими групами (КП). На малюнку 4.2 показані кодові КП для символів з D, Q, і

100001 Тут число нулів завжди парне.

1000001 Тут завжди непарне число нулів

Мал. 4.2 Кодові КП для символів з D, Q, і

Тепер для доведення теореми треба інтерпретує алгоритм записати в термінах кодових груп, шифру програми і шифру конфігурації. Наприклад, крок 1 буде звучати тепер так:

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

Кроки 2 і 3 приймуть такий вигляд:

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

Для кожного кроку інтерпретуючого алгоритму треба побудувати МТ з алфавітом, після чого об'єднати їх належним чином, за допомогою операцій o ||, if-then-else, while-do.

Можливість розв'язання алгоритмічних проблем.

У цьому розділі ми дамо приклади докази нерозв'язності конкретної алгоритмічної проблеми - проблеми самопріменімості.

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

Природно виникає питання: Чи кожна алгоритмічна проблема розв'язана? Аж до початку ХХ століття серед математиків існувала впевненість у можливості розв'язання будь-якої математичної проблеми. Як вже зазначалося у вступі, Лейбніц був один з перших, хто прийшов до ідеї обчислення. Він вважав, що рішення математичної проблеми зводиться до маніпуляції з символами за допомогою спеціальним чином підібраними правилами виведення (заміни одних комбінацій символів на інші). Проблема, на думку Лейбніца, полягала лише в тому, щоб побудувати належним чином систему цих правил. Більш того - він вважав, що можна побудувати універсальний набір правил для вирішення будь-якої математичної проблеми. Джонатан Свіфт у своїй книзі "Пригоди Гуллівера" пожартував над цією ідеєю Лейбніца в образі мудреця, що обертає колеса з табличками в пошуках потрібного рішення.

Англійський математик Черч першим дав приклад нерозв'язною проблемки, відомої як проблема виводимості.

Дана система правил підстановки R і два слова W і S. Чи можна визначити виводиться W з S за допомогою R?

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

Інший відомий нам приклад нерозв'язною алгоритмічної проблеми - 10-я проблема Гільберта.

Визначення 4.2. Алгоритм А називається самопріменімості, якщо він застосуємо до слова, яке є його описом.

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

Теорема 4.1. Розпізнавання самопріменімості алгоритмічно нерозв'язною.

Доказ: Доводити цю теорему будемо методом від противного. Нехай алгоритм А, що розпізнає самопріменімості, існує. Тоді відкоректуємо його так, щоб

не зупиняється, якщо А самопріменім

t - якщо А - трохи самопріменім

Таким чином, В застосуємо до самонепріменімим алгоритмам і не застосуємо до самопріменімості.

Розглянемо У (В), т. Е. Застосування В до самого себе. Якщо В (В) дає t, отже, В - самопріменім, але з побудови В дає t тільки на НЕ самопріменімості авлгорітмах. Якщо В (В) не зупиняється, то це означає, що В - не самопріменім, але з побудови в цьому випадку він повинен дати t. Прийшли до суперечності. Отже, такий алгоритм В не існує. Отже, не може існувати і алгоритм А. Звідси - припущення про існування алгоритму А, що розпізнає самопріменімості, невірно!

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

Взаємозв'язок алгоритмічних систем.

У зв'язку з існуванням нерозв'язних алгоритмічних проблем виникає питання:

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

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

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

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

U (P) = N (P) і навпаки.

Звідси і буде випливати, що якщо якась алгоритмічна проблема розв'язана в МТ, то вона автоматично вирішити в НАМ і навпаки.

Теорема 4.2 Для будь-якої машини Тьюринга U існує НАМ N такий, що

Доказ: Для доказу цієї теореми ми покажемо, як для кожного правила ap®bqw машини U побудувати правило підстановки для НАМ N. Тим самим ми, знаючи функціональну схему U, побудуємо систему правил для N.

У функціональній схемі машини U можуть зустрітися команди наступних видів:

Розглянемо спочатку команди машини U виду (1), т. Е. Запис в поточну позицію замість символу a символу b і зрушення вліво. У відповідному НАМ N ми будемо оброблюваний символ в слові р мітити зліва символом стану т. Е. DN = DU UQU U. Тоді команді (1) можна порівняти наступну групу правил підстановки:

тут символ Ñ "Екранує" q від наступного за ним символу в оброблюваному слові.

Командам виду (2) можна порівняти правила підстановки виду

Командам виду (4) - qj aab.

Самим останнім в системі правил підстановки НАМ буде початкова правило

де qo - початковий стан U.

Зауваження: Якщо а = L, т. Е. Командам Lqj ®bqs w треба буде зіставляти правило qj ®qs b або qj ®bqs в залежності від значення w. Всі такі правила підстановки треба зібрати в кінці схеми, відразу перед початковим правилом.

Зверніть увагу, що якщо на вхід N подати слово, до якого U застосуємо, то N буде нескінченно довго підставляти qo в початок слова.

N застосуємо до тих же словами, що і U.

Припустимо існування слова Р, до якого U застосуємо, а N - немає. Раз U застосуємо, то нехай його заключній командою є команда aq®b! H. Їй з побудови N відповідає термінальне правило підстановки, яке повинно виконуватися, т. К. В схемі N немає двох правил з однаковими правими частинами ..

Прийшли до суперечності.

Доказ теореми 4.2 закінчено.

Теорема 4.3. Для будь-якого НАМ N існує машина Тьюринга U така, що

U * (Р) = * Р, т. Е. МТ. яка ставить символ * перед оброблюваних символом.

U! (P) = P залишилося без зміни слова.