Пример 1. Следующая машина Тьюринга складывает
натуральные числа, записанные в унарной системе счисления.
|
|
q1 |
q2 |
q3 |
|
| |
|q1+1 |
Lq3-1 |
|q3-1 |
|
+ |
|q1+1 |
|
|
|
L |
L q2-1 |
|
Lq0+1 |
Пример 2.
Следующая машина Тьюринга
удваивает натуральные числа, записанные в унарной системе счисления.
|
|
q1 |
q2 |
q3 |
|
| |
aq1+1 |
|q2-1 |
|q3+1 |
|
a |
|
|q3+1 |
|
|
L |
L q2-1 |
Lq0+1 |
|q2-1 |