Задачі для самостійного розв’язування
1. Знайти результат застосування машини Тюрінга із зовнішнім алфавітом А={a0,1}, внутрішнім алфавітом Q={q0,q1,q2,q3,q4,q5,q6,q7} і програмою
q1a0→q4R, q11→q2L, q2a0→q6R, q21→q3L, q3a0→q6R, q31→q1L,
q4a0→q01, q41→q5a0, q5a0→q4R, q51→q5a0, q6a0→q0a0, q61→q7a0,
q7a0→q6R, q71→q7a0 до слів а) 11111; в) 111111; с) 11а0111.
2. Побудувати машини Тюрінга та нормальні алгоритми Маркова, які обчислюють функції: a) f(x)=0; b) f(x)=1; c) f(x)=x; d) f(x,y)=x+y.
3. Нехай E = {a,b,c} та задано таблицю формул підстановок
До якого результату приведе дія цього нормального алгоритму над словом аbb.
4. Винайдіть такий нормальний алгоритм Маркова, за допомогою якого можна перетворити слово «муха» у слово «слон».
Коментарі. Таким чином, ми ознайомились із трьома теоріями, кожна з яких уточнює поняття алгоритму. Докладніше матеріал цього розділу можна знайти в [6,11,16,21,22]. Виникає питання про зв’язки цих теорій між собою. Відповідь на це запитання дає така теорема. Наступні класи числових функцій збігаються:
1) клас усіх частково рекурсивних функцій; 2) клас усіх функцій, обчислювальних за Тюрінгом; 3) клас усіх нормально обчислювальних функцій. Вона означає, що теорії частково рекурсивних функцій, машин Тюрінга і нормальних алгоритмів Маркова рівносильні між собою.
