2. МашинаТьюрінга. Машина Поста. Гіпотеза Черча. Поняття алгоритму.

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

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

Конкретна машина Тьюринга задається перерахуванням елементів множини букв алфавіту A, безлічі станів Q і набором правил, за якими працює машина. Вони мають вигляд: q i a j → q i1 a j1 d k (якщо головка знаходиться в стані q i, а в оглядається комірці записана буква a j, то головка переходить в стан q i1, в клітинку замість a j записується a j1, головка робить рух d k, яке має три варіанти: на клітинку вліво (L), на клітинку вправо (R), залишитися на місці (N)). Для кожної можливої ​​конфігурації "i, a j> є рівно одне правило. Правил немає тільки для заключного стану, потрапивши в яку машина зупиняється. Крім того, необхідно вказати кінцеве і початкове стану, початкову конфігурацію на стрічці і розташування голівки машини. "

Машина Поста (МП) - абстрактна обчислювальна машина, запропонована Емілем Леоном Постом (Emil L. Post), яка відрізняється від машини Тьюринга більшою простотою. Обидві машини "еквівалентні" і були створені для уточнення поняття " алгоритм ".

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

Машину Поста можна розглядати як спрощену модель комп’ютера. Насправді, як комп’ютер, так і машина Поста мають:

• неподільні носії інформації (комірки — біти), які можуть бути заповненими або незаповненими;

• обмежений набір елементарних дій — команд, кожна з яких виконується за один такт (крок).

Машина Поста складається із стрічки та каретки (яка також називається головкою зчитування/запису). Стрічка є безмежною і розділена на комірки однакового розміру. Комірка стрічки може бути порожньою, або у ній може перебувати мітка V. Інформація про те, які комірки порожні, а які містять мітки, утворює стан стрічки. Іншими словами, стан стрічки — це розподіл міток по комірках. Стан стрічки змінюється у процесі роботи машини. Зауважимо, що наявність міток у комірці можна інтерпретувати як «1», а відсутність як «0». Таке двійкове представлення інформації подібне до уявлення, яке використовується практично у всіх сучасних комп’ютерах.

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

1. записати 1 (мітку), перейти до i-го рядка програми;

2. записати 0 (стерти мітку), перейти до i-го рядка програми;

3. переміститися вліво, перейти до i-го рядка програми;

4. переміститися вправо, перейти до i-го рядка програми;

5. зупинка;

6. якщо 0, то перейти до i-го рядка програми, інакше перейти до j-го рядка програми.

Гіпотеза Черча:

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

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