Машина Тюрінга
Машину Тюрінга можна собі уявити, як машину, яка їздить по колії (колія звісно нескінченна в два боки), і малює щось вапном на шпалах. Крім того, вона вміє читати, те, що намалювала на шпалах. Також ця машина має пам’ять ( набір станів).
Машиною Тюрінга з формальної точки зору є впорядкований набір таких елементів:
- Q – скінченна множина внутрішніх станів
- T – скінченний алфавіт символів стрічки. Туди обов’язково має входити символ порожньої клітки — „λ”
- δ:QxT→QxTx{R,L,ε} однозначна функція переходу.
- q0∈Q початковий стан.
- q*∈Q кінцевий стан.
Функція переходу задається множиною записів такого вигляду: pa→qbL, pa→qbR або pa→qb, де p,q∈Q, a,b∈T. Це означає: якщо ми знаходимося в стані p, і читаємо символ a, то переходимо до стану q, записуємо на місці a b, і зміщуємося наліво (L), направо (R), чи залишаємося на місці.
Зазвичай початковим станом q0, вважають такий стан, коли всі символи зліва від головки порожні (λ), а головка показує перший непорожній символ вхідного слова.
При переході до фінального стану q* машина зупиняється.
МТ-обчислювана функція — функція, яку можна обчислити за допомогою машини Тюрінга.
Розглянемо МТ—обчислювані функції над числами в одиничній системі числення. Аргументи будемо розділювати символом дієз (#)
Додавання f(x,y)=x+y
q01→q01R
q0#→q01R
q0λ→q1λL
q11→q*λ
Машина спочатку проходить всі символи зліва направо, замінюючи роздільник на 1. Коли дійшла до кінця (порожнього символа), вертається і стирає зайву одиничку.
Урізана різниця f(x,y)=x-y, якщо x>y, і 0, якщо x≤y
q0#→q4λR
q01→q1λR
q11→q11R
q1#→q1#R
q1λ→q2λL
q21→q3λL
q2#→q*1
q31→q31L
q3#→q3#L
q3λ→q3λR
q41→q4λR
q4λ→q*λ
Віднімання трохи складніше. Ми видаляємо по одній одиничці зліва і зправа, поки, не витремо всі одинички зправа. Якщо залишились тільки праві одинички, це значить, що x<y, і результат нуль. Тоді машина переходить в стан q4, і стирає все. В стані q0 витираємо ліву одиничку, q1 — рухаємося вправо, q2 — витираємо праву одиничку, q3 — рухаємося вліво. Варто зауважити, що ми спочатку витерли ліву, одиничку, і коли при спробі витерти праву, ми виявляємо що її вже немає, то кількість одиничок на стрічці менша на одиницю від потрібної. Тому перехід в кінцевий стан супроводжується додаванням одинички.
А той хто знайде алгоритм добутку з поясненням його роботи — молодець. Я пробував розібратись в тому що в методичці Шкільняка С.С. але виявив там помилку. Також стаття частково за мотивами лекцій.
Напишіть відгук