Машина Тюрінга

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

Машиною Тюрінга з формальної точки зору є впорядкований набір таких елементів:

• Q – скінченна множина внутрішніх станів
• T – скінченний алфавіт символів стрічки. Туди обов’язково має входити символ порожньої клітки — „λ”
• δ:QxT→QxTx{R,L,ε} однозначна функція переходу.
• q₀∈Q початковий стан.
• q^*∈Q кінцевий стан.

Функція переходу задається множиною записів такого вигляду: pa→qbL, pa→qbR або pa→qb, де p,q∈Q, a,b∈T. Це означає: якщо ми знаходимося в стані p, і читаємо символ a, то переходимо до стану q, записуємо на місці a b, і зміщуємося наліво (L), направо (R), чи залишаємося на місці.

Зазвичай початковим станом q₀, вважають такий стан, коли всі символи зліва від головки порожні (λ), а головка показує перший непорожній символ вхідного слова.

При переході до фінального стану q^* машина зупиняється.

МТ-обчислювана функція — функція, яку можна обчислити за допомогою машини Тюрінга.

Розглянемо МТ—обчислювані функції над числами в одиничній системі числення. Аргументи будемо розділювати символом дієз (#)

Додавання f(x,y)=x+y

q₀1→q₀1R
q₀#→q₀1R
q₀λ→q₁λL
q₁1→q^*λ

Машина спочатку проходить всі символи зліва направо, замінюючи роздільник на 1. Коли дійшла до кінця (порожнього символа), вертається і стирає зайву одиничку.

Урізана різниця f(x,y)=x-y, якщо x>y, і 0, якщо x≤y

q₀#→q₄λR
q₀1→q₁λR
q₁1→q₁1R
q₁#→q₁#R
q₁λ→q₂λL
q₂1→q₃λL
q₂#→q^*1
q₃1→q₃1L
q₃#→q₃#L
q₃λ→q₃λR
q₄1→q₄λR
q₄λ→q^*λ

Віднімання трохи складніше. Ми видаляємо по одній одиничці зліва і зправа, поки, не витремо всі одинички зправа. Якщо залишились тільки праві одинички, це значить, що x<y, і результат нуль. Тоді машина переходить в стан q₄, і стирає все. В стані q₀ витираємо ліву одиничку, q₁ — рухаємося вправо, q₂ — витираємо праву одиничку, q₃ — рухаємося вліво. Варто зауважити, що ми спочатку витерли ліву, одиничку, і коли при спробі витерти праву, ми виявляємо що її вже немає, то кількість одиничок на стрічці менша на одиницю від потрібної. Тому перехід в кінцевий стан супроводжується додаванням одинички.

А той хто знайде алгоритм добутку з поясненням його роботи — молодець. Я пробував розібратись в тому що в методичці Шкільняка С.С. але виявив там помилку. Також стаття частково за мотивами лекцій.