lab02_Mashyna_Tjuringa_10_11_2009_print

Довільний скінчений алфавіт

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

якого обмеженого алфавіту.

Загальний випадок опису машини Тьюрінґа – дозволити машині і записувати і рухати головку у тому самому напрямку. Це вимагає заміни початкового 4-х позиційного кортежу на 5-позиційний:

<Стан0, Символ, Станновий, Символновий, Переміщення>

де Символновий є записаним символом, і Переміщення є одним із зсувів вліво і вправо.

Ця додаткова свобода не впливає на нове визначення машини Тьюрінґа.

Тому що для кожної нової машини Тьюрінґа існують старі машини із тими самими властивостями.

Недетерміновані машини Тьюрінґа

Очевидно переформулювання визначення машини Тьюрінґа дозволяє ввести поняття паралельних альтернативних обчислень. У початковому формулюванні було сказано, що машина визначається для багаторазових переходів для заданої пари стан/символ, і може перебувати у такому стані, в

якому обчислення припиняються. У даному переформулюванні,

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

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

11

Введення поняття недетермінованої машини Тьюрінґа не змінює загального визначення машини Тьюрінґа.

Початкове формулювання Тьюрінґом використовувало 5-ти позиціний кортеж для машини Тьюрінґа. Пост запропонував 4-х позиційне представлення і використання безмежної у дві сторони стрічки.

2.2.4. Ускладнення машини Тьюрінґа

Крім виконання арифметичних функцій використовуючи унарне представлення чисел, ми можемо виконувати такі завдання, як копіювання блоків символів, стирання блоків символів тощо. На рис.2.9 зображено приклад машини Тюрінґа, яка після початку роботи із стандартної конфігурації на стрічці, що містить єдиний блок ‘1’, зупиняється на стрічці,

яка містить дві копії цього блоку ‘1’. Блоки розділені ‘0’. Машина Тьюрінґа містить алфавіт, який складається із символів ‘0’, ‘1’ і ‘A’.

Дія цієї машини полягає у повторюваній заміні “1” одного початкового блоку на A, і тоді запис нових ‘1’ справа від решти ‘1’ на стрічці, після залишення нуля між початковим блоком і копією. Тоді машина повертається до блоку із A і перетворює ці символи назад в ‘1’.

Початковий стан s0 використовується для заміни ‘1’ на ‘A’, і

переміщення стрічки вправо з переходом у стан s1. У стані s1 проходимо решту блоку ‘1’ поки не дійдемо до ‘0’ (розділювача блоків) і у стані s2

проходимо всі ‘1’ до найправішого ‘0’ (це є копіювання блоку ‘1’, який ми створюємо). Коли досягнуто кінця блоку машина зчитує ‘0’, який перетворює на ‘1’ і повертає уліво та переходить у стан s3. Стани s3 і s4 переміщають стрічку вліво минаючи всі ‘1’ і розділювач ‘0’ на стрічці доки не дійдемо до

‘A’. Коли машина зчитає символ ‘A’ ми переходимо у стан s0 і рухаємося у право.

У цій точці програма зчитує наступну ‘1’ першого блоку, або перший блок весь складається із символів ‘A’, і зчитує розділювач ‘0’. У

попередньому випадку повторюються дії від стану s1 до стану s4, але в

12

останньому відбувається перехід у стан s5, рухаючись вліво. У цьому випадку ітераційно знаходяться символи ‘A’, які замінюються на ‘1’, та рухається вліво. Якщо зустрічається символ ‘0’, тоді всі символи ‘A’ будуть перетворені назад в ‘1’. Машина буде шукати ‘0’ від початкової комірки, і

таким чином рухатися вправо, і переходити у кінцевий стан s6.

(1,A) (1,>>) (1,>>)

(0,1) (0,>>)

S0 S1 S2

(1,<<) (1,<<)

(0,>>)

S5 S6

(A,1) (1,<<)

Рис.2.9 Приклад машини Тьюрінґа із розширеним зовнішнім алфавітом

Машина копіювання може бути об’єднана із машиною додавання,

представленою на рис.2.4 для створення нової машини, яка здійснюватиме подвоєння числа n до 2n. Це може бути реалізовано спершу виконавши копіювальну машину для отримання стрічки із двома копіями числа n, і тоді

13

застосовуючи машину додавання для обчислення n+n (=2n). Можемо зробити це ідентифікуючи кінцевий стан копіювальної машини (s6) із початковим станом (s0) машини додавання.

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

Перша робота Тьюрінґа зосереджувала увагу на обчислювальних числах.

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

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

наприклад машина для додавання (зображена на рис.2.4), множення, ділення,

взяття експоненти, обчислення факторіалу тощо.

Приймаючи правила представлення TRUE і FALSE (TRUE представимо групою із двох ‘1’, а FALSE однією ‘1’) можна обчислити характеристичні функції обчислювальних предикатів, комбінувати результати таких функцій використовуючи булеві функції: AND, NOT, OR, IF-THEN-ELSE.

Характеристичною функцією довільної множини А U називається функція

А: U {0,1} така: А(а) = 1, якщо а А,

0, якщо а А.

Обчислювальні за Тьюрінґом функції є рекурсивними функціями.

2.2.5. Універсальна машина Тьюрінґа

Різні алгоритми виконуються на різних машинах Тьюрінґа, які відрізняються своїми функціональними схемами. Проте можна побудувати

Універсальну Машину Тьюрінґа (УМТ), яка здатна виконувати будь-який алгоритм, а значить здатну виконувати роботу будь-якої машини Тьюрінґа.

14

Коли УМТ подати стрічку, що містить закодовану іншу машину Тьюрінґа,

назвемо її T, а за нею вхідні дані для T, УМТ отримає той самий результат,

що і T. УМТ може наслідувати поведінку будь-якої машини Тьюрінґа

(включаючи себе).

УМТ можна вважати програмованим комп’ютером. Коли УМТ надати програму (опис іншої машини), вона функціонуватиме, ніби це задана машина обробляє вхідну стрічку. Слід зауважити ідентифікацію еквівалентності введення-виведення до “функціонує еквівалентно ”. Машина

T працюючи над введеною інформацією t ймовірно виконуватиме менше переміщень ніж УМТ, яка симулює машину T яка обробляє t.

Для того, щоб спроектувати таку машину спершу необхідно визначити представлення машини Тьюрінґа на стрічці для оброблення УМТ. Щоб зробити це, необхідно нагадати, що машина Тьюрінґа формально представляється набором 4-х позиційних кортежів. Спершу закодуємо однин кортеж, а потім весь набір.

Кожний 4-х позиційний кортеж у специфікації машини буде закодований як набір чотирьох блоків ‘1’, розділених одним ‘0’

1.Перший блок одиниць кодуватиме біжучий стан,

використовуючи прийняте нами положення про унарні числа

(n+1 одиниць представляє число n).

2.Другий блок одиниць кодує біжучий символ,

використовуючи ‘1’ для представлення цифри нуль, і дві для

представлення цифри ‘1’ (не можна використати нуль для

представлення ‘0’.)

3.Третій елемент кортежа представлятиме новий стан в унарній нотації.

4.Четвертий елемент представлятиме дію, і існує 4

можливості: символи будуть кодовані аналогічно, як це зроблено вище.

Блок із трьох ‘1’ представлятиме рух вліво («), а блок із чотирьох ‘1’

представлятиме рух вправо (»).

15

Використовуючи таке положення кортеж <0, ‘1’, 0, »> можна представити стрічкою, зображеною на рис.2.10.

Рис.2.10. Кодування кортежу <0, ‘1’, 0, »>

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

… 010110101111 00 101011011 00 110110110111 00 11010111011110 …

Рис.2.11. Кодування машини Тьюрінґа, зображеній на рис.2.3

Якщо інтерпретувати кодування на рис.2.10 як бінарне число (ігноруючи подвійні нулі), тоді кожна машина Тьюрінґа має свій серійний номер.

2.2.6. Формальне визначення

Визначення: Пiд (детермінованою) машиною Тьюрiнґа (МТ) будемо розумiти впорядковану 5-ку (Q,T, , q0 ,q*),

де Q – скiнченна множина внутрiшнiх станів;

T – скiнченний алфавiт символiв стрiчки, причому T мiстить спецiальний символ порожньої комірки ;

– Q T→Q T {R,L, } однозначна функцiя переходiв; q0 Q – початковий стан;

q* Q – фiнальний стан.

Функцiю переходiв задають скiнченною множиною команд одного з 3-х

видiв: qa pbR, qa pbL та qa pb, де p, q Q, a, b T, Q T. При

16

цьому, як правило, не для всiх пар (q,a) Q T iснує команда з лiвою частиною qa. Це означає, що функцiя не є тотальною. Проте зручніше вважати функцію тотальною, тому для всiх пар (q,a) D неявно (не додаючи вiдповiднi команди вигляду qa qa), вводимо довизначення (q,a)=(q,a, ).

Неформально МТ складається з скiнченної пам’яті, розділеної на комірки нескiнченної з обох бокiв стрiчки та головки читання-запису. В

кожнiй клiтцi стрiчки мiститься єдиний символ iз T, причому в кожен даний момент стрiчка мiстить скiнченну кiлькiсть символiв, вiдмiнних вiд символа

. Голiвка читання-запису в кожен даний момент оглядає єдину клiтку стрiчки.

Якщо МТ знаходиться в станi q та голiвка читає символ a, то при виконаннi команди qa pbR (команди qa pbL, команди qa pb) МТ переходить в стан p, замiсть символу a записує на стрiчцi символ b та змiщує голiвку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає голiвку на мiсцi).

Конфiгурацiя, або повний стан МТ це слово вигляду xqy, де x,y T*, q Q. Неформально це означає, що на стрiчцi записане слово xy, тобто злiва i

справа вiд xy можуть стояти тiльки символи , МТ знаходиться в станi q,

голiвка читає 1-й символ пiдслова y.

Конфiгурацiю вигляду q0x, де 1-й та останнiй символи слова x вiдмiннi

вiд , називають початковою. Конфiгурацiю вигляду xq*y називають

фiнальною. Пiсля переходу до фiнального стану, отже, до фiнальної конфiгурацiї, МТ зупиняється.

Нехай МТ знаходиться в конфiгурацiї xcqay, де x,y T*, a, c T, q Q.

Пiсля виконання команди qa pbR (команди qa pbL, команди qa pb) МТ перейде до конфiгурацiї xcbpy (вiдповiдно до xpcby, конфiгурацiї xcpby).

Кожна МТ задає вербальне вiдображення T* →T* таким чином.

МТ М переводить слово u T в слово v T*, якщо вона з початкової конфiгурацiї q0u переходить до фiнальної конфiгурацiї xqy, де q F*, xy= v ,

17

, { }* . При цьому перший та останнiй символи слова v вiдмiннi вiд ,

або v= . Цей факт записуємо так: v=M(u).

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

не визначене.

МТ M1 та M2 еквiвалентнi, якщо вони задають одне і те ж вербальне вiдображення.

МТ M обчислює часткову функцiю f:Nk→N якщо вона кожне слово

Функцiя називається обчислюваною за Тьюрiнгом, або МТ-

обчислюваною, якщо iснує МТ, яка її обчислює.

3.КОНТРОЛЬНІ ЗАПИТАННЯ

1.З чого складається машина Тьюрінґа? Які дії вона виконує?

2.За допомогою чого описують машину Тьюрінґа? Наведіть приклади схем машин Тьюрінґа.

3.Що називають композицією машин Тьюрінґа?

4.В чому полягає задача універсального алгоритму?

5.Що таке універсальна машина Тюрінґа?

4.ЛАБОРАТОРНЕ ЗАВДАННЯ

1.Ознайомитись з принципами функціонування машини Тьюрінґа.

2.Одержати індивідуальне завдання (див. Варіанти індивідуальних завдань).

3.Скласти граф-схему алгоритму та програму для машини Тьюрінґа.

4.Виконати програму.

18

5.ЗМІСТ ЗВІТУ

1.Мета роботи.

2.Теоретичний аналіз опрацьованого матеріалу.

3.Відповіді на контрольні запитання.

4.Індивідуальне завдання, отримане у викладача.

5.Аналіз отриманих результатів і висновки.

6.Список використаної літератури.

СПИСОК ЛІТЕРАТУРИ

1.Алферова З.А. Теория алгоритмов. — М.: Статистика, 1973.

2.М.Брой. Информатика. В 3 томах. Т.1. Основополагающее введение. —

М.: Диалог-МИФИ, 1996.

3.Основы кибернетики. Математические основы кибернетики./Под ред.

К.А.Пупкова — М.,Высшая школа, 1974.

4.Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. — М.:

Сов.радио, 1974.

5.Успенский В.А. Машина Поста. — М. Наука, 1988.

6.Манин Ю.И. Вычислимая и невычислимое. — М.: Сов. радио, 1980.

7.Мальцев А.И. Алгоритмы и вычислимые функции. — М.: Наука, 1986.

8.Марков А.А., Нагорный Н.М. Теория алгорифмов. — М.: Наука, 1984.

9.Матюшков Л.П., Лихтарович А.А. Основы машинной математики:

Пособие для учителя. — Минск: Нар.Асвета, 1988.

10.Машины Тьюринга и вычислимые функции: Пер. с нем. — М.: Мир, 1972.

11.Миков А.И. Информатика. Введение в компьютерные науки. — Пермь,

ПГУ, 1998.

19

ВАРІАНТИ ІНДИВІДУАЛЬНИХ ЗАВДАНЬ

Варіант 1

На інформаційній стрічці машини Тюрінґа розташований масив символів +.

Необхідно розробити функціональну схему машини Тюрінґа, яка кожний другий символ + замінить на –. Каретка у початковому стані q0 знаходиться над першим лівим елементом масиву.

Варіант 2

Задано число n у вісімковій системі числення. Розробити машину Тюрінґа,

яка збільшувала б задане число n на 1.

Варіант 3

Задано десятковий запис натурального числа n>1. Розробити машину Тюрінґа, яка б зменшувала задане число n на 1. При цьому запис числа n-1 не повинен містити лівий нуль, наприклад, 100-1=99, а не 099. Початкове положення головки – над крайнім правим символом.

Варіант 4

Задано масив з дужок, що відкриваються і закриваються. Побудувати машину Тюрінґа, яка видаляла б пари взаємних дужок.

Наприклад, початковий стан: « ) ( ( ) ( ( ) », кінцевий стан: « ) . . . ( ( . ».

Варіант 5

Задано стрічку з символів «a» і «b». Розробити машину Тюрінґа, яка перемістить всі букви «a» у ліву, а символи «b» — у праву частину стрічки.

Каретка знаходиться над крайнім лівим символом стрічки.

Варіант 6

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

20