Последовательность работы машины Тьюринга

1) Чтение входной переменной

2) Замещение ее выходной переменной

3) Перемещение в соответствии с управлением

4) Установка следующего состояния

Например: дана машина Тьюринга, которая должна осуществлять организацию алгоритма сложения 2-х чисел (целых и представленных в виде последовательности единиц).

Пустой символ – Λ

- входной алфавит.

Алгоритм управления {П, Л, Н};

Алгоритм состояний {S₁, S₂, S₃}

! – стоп-состояние, останов алгоритма.

Исходное состояние S₁

I такт

1)вместо 1 запишется Λ;

2)перемещение вправо;

3)переход в S₃.

II такт

1) записываем 1;

2)перемещение вправо;

3)переход в S₃.

……..

V такт

1) записываем +;

2)перемещение вправо;

3)переход в S₃.

…..

XII такт

На входе пустое поле (Λ)

1) записываем 1;

2)не перемещаемся;

3)переход в S₂.

XIII такт

На входе 1

1) записываем 1;

2) перемещение влево;

3)переход в S₂.

……

(N-1) такт

Пустой на входе

1) записываем Λ;

2) перемещение вправо;

3)переход в S₁.

N такт

На входе +

1) записываем Λ;

2) не перемещаемся;

3)останов алгоритма.

Начальное входное слово 1111+111111, конечное выходное слово 1111111111.

Машина Тьюринга может реализовывать бесконечное множество различных алгоритмов. Но некоторые задачи не могут быть решены с помощью машины Тьюринга.

Машина Тьюринга представляет собой простейшую систему для реализации алгоритмов.

Алгоритм в ней реализуется на наиболее низком уровне, поэтому более сложные подходы к реализации алгоритмов содержат внутри себя подалгоритмы, реализуемые с помощью машины Тьюринга.

Это позволило сформулировать тезис Тьюринга: функция вычислена с помощью какого-нибудь алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга.

Рассмотрим в качестве примера машину Тьюринга, алгоритм работы которой задан следующей функциональной схемой.

Необходимо смоделировать работу данной машины и выявить реализуемую ей математическую зависимость.

Исходное состояние S0, символ 11*111

1. S0 11*111 П,S2;

⌂

2. S2 а1*111 П,S2;

⌂

3. S2 а1*111 П,S2;

⌂

4. S2 а1*111 П,S2;

⌂

5. S2 а1*111 П,S2;

⌂

6. S2 а1*111 П,S2;

⌂

7. S2 а1*111^ H,S1;

⌂

8. S1 а1*1111 Л,S1;

⌂

9. S1 а1*1111 Л,S1;

⌂

10. S1 а1*1111 Л,S1;

⌂

11. S1 а1*1111 Л,S1;

⌂

12. S1 а1*1111 Л,S1;

……… ⌂

14. S1 а1*1111 П,S0;

⌂

15. S0 а1*1111 П,S2;

⌂

16. S2 аа*1111 П,S2;

…………

S1 аа*11111 Л,S1;

………………..ааа111111

Это алгоритм умножения.

Для некоторых алгоритмов процесс их выполнения зависит от исходных данных. При некоторых исходных данных цикл работы можно считать бесконечным.