Мова переходів для Машини Тюринга

Визначення

Програма для машини Тюринга складається із набору правил переходів.

Кожне правило переходу складається з умови та команди переходу.

Умова переходу визначає який поточний стан та який символ на каретці задовольняють умову для виконання команди даного переходу.

Команда переходу визначає 3 дії, які може виконувати машина Тюринга:

  • Який символ записати у комірку під катеркою
  • У яку сторону зсунути карету (вправо-вліво на 1 позицію)
  • У який стан переходить машина після виконання перших двох дій

Початковий стан машини буде поточним станом першого переходу програми.

Кінцевий стан почначається символом знаку оклику!.

Лексеми

Регістр символів у програмі важливий.

Назва стану машини може містити будь-які друковані символи Unicode окрім пробільних та символу коми ,. Наприклад, q1, q', 1, state_1, стан-1.

Символ у комірці стрічки може бути будь-яким друкованим символом Unicode окрім коми ,.

Напрямок руху каретки при виконанні машиною команди кодується одним із трьох символів:

  • L - рух вліво
  • N - не виконувати рух
  • R - рух вправо

Синтаксис

Програма задається як послідовність переходів. Кожен перехід починається з нового рядка, пусті рядки ігноруються.

перехід1
перехід2

перехід3
перехідN

Перехід складається із умови та команди, що розділені символами ->:

умова->команда

Перехід завжди починається з нового рядка і не містить символів перед умовою чи після команди.

Умова переходу складається з назви поточного стану та поточного символу, що розділені комою ,: q1,g, stateN,#, 1,_.

Команда переходу складається із нового символа, напрямку руху каретки та нового стану, що розділені комами: f,R,state2, *,N,q2, _,R,1.

При цьому кожну із частин команди можна упускати - це означатиме, що відповідна дія не виконуватиметься:

  • ,R,q1 - символ під кареткою залишається незмінним
  • f,,q1 - каретка не рухається (аналогічно f,N,q1)
  • f,R, - стан машини не змінюватиметься

Тоді повний перехід позначатиметься так:

q1,a->b,R,q2

А програма виглядатиме так:

q0,h->H,R,q0
q0,e->E,R,q0
q0,l->L,R,q0
q0,o->O,R,q0
q0,.->!,R,q1
q1, -> ,L,!

Можливі помилки парсингу програми

Синтаксичні помилки

  1. Текст програми пустий - не можна запрограмувати машину без переходів
  2. Недозволений символ у назві поточного стану: q 1,a->b,R,q2
  3. Стан не задано: ,a->b,,
  4. Недозволений поточний символ: q,,->b,,
  5. Поточний символ не задано: q,->b,,
  6. Поточний символ складається з багатьох символів: q,xx->b,,
  7. Очікується символ > після символу -: q,a-b,,
  8. Недозволений символ заміни: q,a->,,R,q2
  9. Символ заміни складається з багатьох символів: q,a->xx,,
  10. Задано невірний напрямок руху каретки: q,a->b,T,q2
  11. Недозволений символ у назві нового стану: q1,a->b,R,new state
  12. Неповний перехід: q1,, q1,x, q1,x->, q1,x->,, q1,x->,R,

Семантичні помилки

  1. Перехід з такою умовою вже існує
  2. Жоден перехід програми не переводить машину у цей стан - початковий стан не враховується
  3. Перехід у новий стан, що не визначений у програмі - кінцевий стан не враховується
  4. Пасивна команда зациклить машину - якщо команда не перезаписує символ, не робить рух та не переходить у новий стан

Помилки виконання програми машиною

  1. Не знайдено перехід, що задовольняє поточну умову машини
  2. Перевищено допустиму довжину стрічки - максимальна довжина стрічки задається у налаштуваннях машини. Потрібно для виявлення зациклення, наприклад, такою програмою:
    q, ->a,R,q
q,b->,,!
    із пустою стрічкою на вході
  3. Перевищено максимальну кількість кроків виконання - максимальна кількість кроків виконнання задається у налаштуваннях машини. Потрібно для виявлення зациклення, наприклад, такою програмою:
    q1, ->,R,q2
q2, ->,L,q1
q2,x->,,!
    із пустою стрічкою на вході