Конфигурационное представление работы машины Тьюринга.

Нулевой шаг программы
(Обозначает слово) #→ #R (замещает слово)

#

+

#

↑- считывающая головка

9. 1→ 1R

#

+

#

↑- считывающая головка

10. 1→ 1R

#

+

#

↑- считывающая головка

11. 1→ 1R

#

+

#

↑- считывающая головка

12. +→ 1R

#

#

↑- считывающая головка

13. 1→ 1R

#

#

↑- считывающая головка

14. 1→ 1R

#

#

↑- считывающая головка

15. #→ #L

#

#

↑- считывающая головка

16. 1→ #L

#

#

#

↑- считывающая головка

Дополнительные сведения

1) 1→ 1R переход на 1 знак вправо;

2) +→ 1R когда встречается другой символ у нас изменяется q, замена символа и переход на следующий шаг;

3) #→ #L шал влево и изменение q;

4) 1→ #L замена символа и остановка программы.

Конечное состояние ленты с данными

Запись на ленте будет называться словом. Конфигурацией машины Тьюринга называют слово, положение считывающей головки и внутренним стостоянием. Конфигурацию записывают в виде: , … … где – буква, головка обозначает символ , состояние .

Дата добавления: 2015-08-17