TuringMachineSimulator

Программа нужна чтобы отслеживать ход машины Тюринга при подсчете функций:

Например, можно подсчитать функцию [1/(x-3)] + y.

Вот программы, задающие эту функцию:

• q1 1 q2 0 R
• q1 0 q9 0 R
• q2 1 q3 0 R
• q2 0 q9 0 R
• q3 1 q4 0 R
• q3 0 q9 0 R
• q4 1 q5 0 R
• q4 0 q9 0 R
• q5 1 q6 0 R
• q5 0 q5 0 S
• q6 0 q0 0 S
• q6 1 q7 0 R
• q7 1 q7 0 R
• q7 0 q8 0 R
• q8 1 q0 0 S
• q8 0 q9 0 R
• q9 1 q10 0 R
• q9 0 q10 0 S
• q10 0 q10 0 S
• q10 1 q0 0 S

Используя их, мы можем отслеживать ход работы алгоритма.

Ещё пример: f(x,y) = ( 2 + x ) / ( 2 - x )

• q1 1 q1 1 R
• q1 0 q2 0 R
• q2 1 q3 0 R
• q3 0 q4 0 L
• q4 0 q4 0 L
• q4 1 q5 1 L
• q5 1 q6 0 L
• q6 1 q5 1 L
• q5 0 q0 0 S
• q6 0 q6 0 S
• q3 1 q7 1 R
• q7 1 q7 1 S
• q7 0 q8 0 L
• q8 1 q8 1 L
• q8 0 q9 0 L
• q9 1 q9 1 L
• q9 0 q0 0 S

---

f(x,y) = max(x,y)

• q1 1 q2 0 R
• q2 1 q2 1 R
• q2 0 q3 0 R
• q3 1 q3 1 R
• q3 0 q4 0 L
• q4 1 q5 0 L
• q5 1 q5 1 L
• q5 0 q6 0 L
• q6 1 q6 1 L
• q6 0 q1 1 R
• q1 0 q7 0 R
• q7 1 q0 0 R
• q4 0 q0 0 S
• q7 0 q7 0 L

---

#Ещё один тип задач:

Если передать false в конструктор, то будет демонстрировать другой тип задачь.

Например:

1. Написать программу машины Тьюринга, переводящую конфигурацию q1 1^(n+10) 0^(m+1) в конфигурацию q0 1, если n и m четны, и в q0 0 в остальных случаях.

• q1 1 q2 B R
• q2 1 q3 B R
• q3 1 q2 B R
• q3 0 q4 B R
• q4 0 q4 B R
• q4 B q0 0 S
• q2 0 q5 B R
• q5 0 q6 B R
• q6 0 q5 B R
• q5 B q0 1 S
• q6 B q0 0 S

Данная программа будет демонстрорвать переход к нужной конфигурации!

Написать программу машины Тьюринга, переводящую конфигурацию q1 1^(n+10) 0^(m+1) в конфигурацию q0 0, если m > n или m − n четно, и в q0 1 в остальных случаях.

• q1 1 q2 B R
• q2 1 q2 1 R
• q2 0 q3 0 R
• q3 B q4 B L
• q4 0 q5 B L
• q5 0 q5 0 L
• q5 1 q6 1 L
• q6 1 q6 1 L
• q6 B q1 B R
• q2 B q7 B L
• q7 1 q7 B L
• q7 B q0 0 S
• q5 B q8 B R
• q8 0 q9 B R
• q9 0 q8 B R
• q8 B q0 1 S
• q9 B q0 0 S
• q3 0 q3 0 R