НОУ ІНТУЇТ | лекція | Алгоритми: машини Тьюринга

1. Основні визначення

Наша взаимовыгодная связь https://banwar.org/

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

Основні визначення

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

Машина Тьюринга (м.т.) складається з необмеженої в обидві сторони стрічки, розбитою на осередки, по якій пересувається головка машини. Така "нескінченність" стрічки є математичною абстракцією, що відбиває потенційну необмеженість пам'яті обчислювача. Зрозуміло, в кожному завершується обчисленні використовується тільки кінцева частина цієї пам'яті - кінцеве число осередків. У кожному осередку стрічки записаний один символ з кінцевого зовнішнього алфавіту машини . Головка машини являє кінцевий автомат, який в кожен момент часу знаходиться в одному з внутрішніх станів Q = {q0, q1, ..., qn}. На кожному кроці головка в залежності від свого внутрішнього стану і символу в комірці, яку вона спостерігає, змінює свій внутрішній стан і вміст спостерігається осередки і може зрушити на одну клітинку вправо або вліво або залишитися на місці.

Дамо більш формальне визначення.

Визначення 9.1. Машина Тьюринга - це система виду

що включає наступні компоненти:

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

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

Як і для кінцевих автоматів, програму P можна задавати за допомогою таблиці розміру nxm, рядки якої відповідають станам з Q, а стовпці - символам з вхідного алфавіту в якій на перетині рядка qi і шпальти aj варто трійка qk al C - права частина команди qi aj -> qk al C.

Визначення 9.2. Назвемо конфігурацією М.Т. в певний момент часу слово K = Wл qi aj Wп, де - слово на стрічці лівіше текушего положення головки, qi - внутрішній стан в даний момент, aj - символ, оглядає головкою, - слово на стрічці правіше текушего положення головки.

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

Початкова конфігурація - це конфігурація виду q0w, тобто в початковий момент часу головка в стані q0 оглядає перший символ вхідного слова w. {It Заключна} конфігурація - це конфігурація виду w1 qf w2, в якій машина знаходиться в заключному стані qf.

Визначення 9.3. Скажімо, що конфігурація K = w1 qi aj w2 м.т. за один крок (такт) переходить в конфігурацію , Якщо в програмі є команда qi aj -> qk al C і при цьому,

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

Приклад 9.1.

Виконання команди q3 0 -> q5 1 П

Наприклад, ситуації, представленої на рис.9.1 зліва відповідає конфігурація . Припустимо, що програма P містить команду q30 -> q51 П. Тоді після виконання цієї команди K перейде за один крок в конфігурацію , Показану на цьому малюнку праворуч. отже, .

Визначення 9.4. Обчислення м.т. на вході w - це кінцева або нескінченна послідовність конфігурацій така, що K0 = q0w - початкова конфігурація. Ця послідовність кінцева, коли її остання конфігурація Kn = v1 qf v2 - заключна. У цьому випадку обчислення назвемо результативним, а слово v = v1 v2 - його результатом на вході w (завжди будемо припускати, що v не містить порожніх символів зліва і справа).

Визначення 9.5. Скажімо, що м.т. обчислює часткову словникову функцію якщо для кожного слова w з області визначення f існує результативне обчислення з результатом , А якщо f (w) не визначена , То обчислення на вході w нескінченно.

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

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

Визначення 9.6. Скажімо, що м.т. обчислює часткову арифметичну функцію f: Nk -> N, якщо для будь-якого набору чисел (x1, x2, ..., xk), на якому f визначена, існує результативне обчислення на вході з результатом , а якщо , То обчислення на відповідному вході нескінченно.

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