Тема 16. Побудова комбінаторних алгоритмів і алгоритмів побудови баз даних
Алгоритмічні системи.
Питання теми
1. Алгоритми Поста.
2. Машини Тьюринга.
3. Алгоритмічна система Маркова.
Основні терміни теми : машини Поста, машини Тьюринга, система Маркова.
1. Алгоритми Поста
Як уже було сказано, існує алгоритмічних систем: система нормальних алгоритмів Маркова, система Поста, система Тьюринга, система Колмогорова-Успенського та ін. Розглянемо більш детально лише три - машини Поста, машини Тьюринга і нормальні алгоритми Маркова.
Алгоритмічна система, запропонована в 1936 p. E. Постом і названа машинами Поста, це - спеціальний клас алгоритмів. Для машин Поста вхідна і вихідна інформації задаються в алфавіті Х= (0, 1}, а алгоритм - у вигляді скінченного упорядкованого набору правил (команд), які називаються наказами. Для запису вхідної, вихідної і проміжної інформації служить гіпотетична нескінченна в обидві сторони інформаційна стрічка, поділена на окремі клітинки, в кожній з яких можна розмістити лише одну букву: 0 або 1. Ті клітинки, в яких записані одиниці, називаються відміченими, а ті, в яких записані нулі, - невідміченими.
Робота алгоритму проходить дискретними кроками, на кожно¬му виконується один з наказів, що складають алгоритм. Кожному такому кроку відповідає цілком визначена активна клітинка на інформаційній стрічці. Для першого наказу алгоритму фіксується як активна деяка початкова клітинка. Подальші зміни місцезнаходження активної клітинки на стрічці повинні передба¬чатися в самому алгоритмі. Накази, які складають алгоритм, мо¬жуть належати до одного із таких шести типів.
Перший тип. Відмітити активну клітинку (записати в неї одиницю) і перейти до виконання і-го наказу (і - може бути довільним числом із чисел, які використані для нумерації наказів алгоритму).
Другий тип. Стерти відмітку активної клітинки (записати в неї нуль) і перейти до виконання і-го наказу.
Третій тип. Змістити активну клітинку на один крок вправо і перейти до виконання і-го наказу.
Четвертий тип. Змістити активну клітинку на один крок вліво і перейти до виконання і-го наказу.
П'ятий тип. Якщо активна клітинка відмічена (якщо в ній записана одиниця), то перейти до виконання j-ro наказу, а якщо не відмічена (якщо в ній записаний нуль), - до виконання і-го наказу.
Шостий тип. Зупинка, закінчення роботи алгоритму.
Алгоритми, які складаються із скінченного числа наказів перелічених типів, називаються алгоритмами Поста. Отже, для того щоб задати машину Поста, необхідно задати таку четвірку (X - {0, 1}, активну клітину, # - спеціальний пустий символ, Р - алгоритм).
Робота машини Поста полягає у виконанні наказів алгоритму функціонування машини. Машина зупиняється тоді і тільки тоді, коли останнім виконаним наказом машини є наказ шостого типу. І результатом її роботи є слово q, яке записане на інформаційній стрічці і яке називається заключним. Отже, машина Поста переробляє вихідні слова у заключні, тобто обчислює значення деякої словарної функції fn в алфавіті X, для якої вихідні слова є її аргументами, а заключне слово -*- значенням цієї функції. Якщо машина Поста зупиняється з деяким словом на інформаційній стрічці, то функція, що визначена цією машиною, вважається визначеною. А якщо машина Поста не зупиняється, то значення відповідної функції вважається невизначеним. При інтерпретації заключного слова як значення функції пусті символи # ігно¬руються.
Доведено, що алгоритм Поста обчислює деяку частково рекурсивну функцію, і, навпаки, всяка частково рекурсивна функція може бути обчислена відповідним алгоритмом Поста. Інакше кажучи, має місце таке твердження: клас всіх алгоритмів, еквівалентних алгоритмам Поста, співпадає з класом всіх частково рекурсивних функцій.
Приклад алгоритму Поста
Покажемо, що найпростіша функція S(n) = n + 1 обчислюється на машині Поста. Для цього подамо число n в двійковій системі числення, тобто в алфавіті X = {0, 1}, запишемо його на інформаційну стрічку і встановимо активну клітину, в якій знаходиться перший символ числа n (його старший двійковий розряд). Тоді алгоритм Р функціонування машини Поста має такий вигляд:
1. Якщо в активній клітинці 0 то перейти до виконання 2, інакше перейти до виконання 3.
2. Змістити активну клітинку на один крок вправо і перейти до виконання 1.
3. Якщо в активній клітинці 1, то перейти до виконання 2, інакше перейти до виконання 4.
4. Змістити активну клітину на один крок вправо і перейти до виконання 5,
5. Якщо в активній клітинці 0, то перейти до виконання 6, інакше перейти до виконання 7.
6. Записати в активній клітинку 1 і виконати команду СТОП.
7. Записати в активну клітинку 0 і перейти до виконання 8.
8. Змістити активну клітинку на один крок вліво і перейти до виконання 9.
9. Якщо в активній клітинці 0, то перейти до виконання 6, інакше перейти до виконання 10.
10. Якщо в активній клітинці #, то перейти до виконання 6, інакше перейти до виконання 7.
Тестування цього алгоритму пропонується виконати як вправу.
2. Машини Тьюринга
До описаної алгоритмічної системи Поста дуже близька система Тьюринга, яку називають машинами Тьюринга. У цій системі також виконується запис інформації на нескінченній в обидві сторони стрічці, розбитій на клітинки. Але, на відміну від системи Поста, тут для запису інформації використовується довільний скінченний алфавіт X = {х1, х2, ..., хn}.
Рис 1. Схема машини Тьюринга
Кожна клітинка інформаційної стрічки служить для запису лише однієї букви. Ця буква може оглядатися спеціальним чутливим елементом так званої головки машини Тьюринга (Т), яка має змогу пересуватися вздовж інформаційної стрічки в обидві сторони. Головка машини Тьюринга може знаходитись в скінченному числі різних станів qr q2,..., qm, друкувати в клітинці, яку оглядає головка, будь-яку букву х1, х2, ..., хm і залишатись на місці або переміщува¬тися вправо чи вліво вздовж інформаційної стрічки на одну клітинку.
Задати машину Тьюринга означає задати таку п'ятірку (X, Q, qo, #, Р), де:
X - алфавіт машини;
Q - скінченна непуста множина станів машини (X Ç Q = 0);
qo - початковий стан машини (q0 є Q);
# - спеціальний "пустий" символ, такий що # є X È Q;
Р - програма роботи машини.
Програма роботи машини - це скінченна множина п'ятірок вигляду xqyq's, кожна така п'ятірка називається командою і виконання команди xqyq's означає, що коли головка машини Тьюринга знаходиться в стані q і читає записану в клітинці стрічки букву х, то вона записує на місці цієї букви х нову букву у (яка може співпадати з х), переходить в стан q' (який може співпадати зі станом q) і переміщується вздовж стрічки на величину s = 0, ±1.
Робота машини Тьюринга полягає в повторенні такого циклу дій, які є спільними для будь-якої машини Тьюринга:
а) читання символу з клітинки, яку оглядає головка;
б) пошук застосовної команди, тобто пошук команди xqyq's, у якій q - стан головки в данний момент часу, ах - символ в клітинці, яку оглядає головка;
в) виконання знайденої команди.
При цьому вважається, що в програмі не існує таких двох команд, які б мали однаковими перші два символи.
Машина Тьюринга зупиняється в тому і тільки в тому випадку, коли ні одна з команд її програми не застосовна. Результатом роботи машини після її зупинки є слово, яке записане на стрічці. Після цього машина Тьюринга стає алгоритмічною системою. При цьому вона обробляє заздалегідь записане на стрічці слово або нескінченно довго, або зупиняється після скінченного числа кро¬ків. У першому випадку вважається, що алгоритм, який виконуєть¬ся машиною, не застосовний до вхідного слова р, а в другому випадку слово, яке залишається на стрічці після зупинки машини, приймається як вихідне, до якого машина перетворює задане вхідне слово р.
Для машин Тьюринга, як і для машин Поста, має місце:
Теорема 1. Всяка частково рекурсивна функція може бути реалізована за допомогою деякої машини Тьюринга і, навпаки, всяка машина Тьюринга реалізує деяку частково рекурсивну функ-цію.
3. Алгоритмічна система Маркова
Алгоритмічна система Маркова будується майже за тими ж принципами, що і попередні системи Поста і Тьюринга, але на відміну від них носить дещо простіший і інтуїтивно більш зрозумілий характер.
Нехай X - деякий скінченний алфавіт, F(X) - напівгрупа слів у цьому алфавіті і е є F(X), де е - пусте слово. Якщо р, q є F(X), то вирази р —> q і р —>.q називаються формулами підстановки в алфавіті X. При цьому вважається, що символи —> і. не належать алфавіту X, а слова р і q можуть бути пустими.
Формула підстановки р —> q називається простою, а формула підстановки р —>.q - заключною.
Нехай вираз р —» [.] q означає будь-яку із формул підстановки р —> q або р —>.q. Скінченна послідовність R формул підстановки в алфавіті X називається схемою або системою переписування. Всяка система переписування є функція f: F(X) —> F(X), значення якої обчислюєть¬ся за такими правилами:
(1) Якщо ніяке з слів р, (і = 1,2,..., 1) не є під словом слова р, то р залишається без змін і є результатом переписування. Цей факт будемо записувати у вигляді R: р!.
(2) Якщо серед слів р1 р2,..., p1 існують такі, що є підсловами слова р, то нехай m - таке найменше число, що 1 < m < 1 і рm - підслово слова р. Слово р', яке одержане в результаті підстановки самого лівого входження (першого входження) слова рт словом qm в слові р, будемо позначати R: р Г р'.
Робота за даними правилами може завершитися з двох причин:
а) якщо формула підстановки р —>[.] q заключна;
б) якщо R: р = q означає, що існує така послідовність r0 , r1 ,... ..., rk слів із F(X), що р = r0, q = rk і R: гi – гi+1 для і = 1, 2,..., k-2 і або R : rk!, a6o R: rkl—>. rk.
Функція f: F(X) —> F(X), визначена таким чином, називається нормальним алгорифмом Маркова в алфавіті X.
Робота алгорифму R може бути описана так. Нехай р є F(X). Знаходимо в R першу формулу підстановки pm —>[.]qm, таку що р - підслово слова р. Виконуємо заміну першого входження слова р словом qm в слові р. Якщо р' - результат цієї підстановки, то коли pm —>[.]qm заключна, то робота алгорифму закінчується і результатом є слово р'. Якщо формула підстановки рm—>[.]q проста, то до слова р' застосовується той же пошук, що і до слова р і т.д. Якщо, нарешті одержується таке слово гi, що R: г.!, тобто ні одне із слів pi, і = 1, 2, ..., 1, не є підсловом слова г, то робота алгорифму закінчується і гi буде його значенням.
З вище сказаного випливає, що можлива ситуація, коли описаний процес ніколи не закінчиться. У цьому випадку будемо говорити, що алгорифм R незастосовний до слова р.
Приклад 1. Нехай X = {a, b}, a R має вигляд
Алгорифм R переписує всяке слово р із F(X), яке має хоча б одну букву а, в слово, яке одержується з р шляхом викреслювання першого входження букви а в слово р. Ясно також, що R(e) = е і R не застосовний до непустих слів із F(X), які не мають входження букви а.