4.4. Примеры машин

 

Пример 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