Машина Тьюринга

1.

Машина Тьюринга

2.

Машина Тьюринга
Это математическая
(воображаемая)
машина. Она
является
математическим
объектом и
отражает
объективную
реальность,
моделирует некие
реальные процессы

3.

Машина располагает:
Внешним алфавитом A={a0,a1,…an}
В каждую ячейку обозреваемой
ленты в каждый дискретный момент
времени может быть записан только
один элемент из алфавита А
a0-пустая буква и именно она
записана в пустую ячейку ленты

4.

Лента является неограниченной в
обе стороны

5.

В каждый момент времени
машина способная находиться в
одном из состоянии
Q = {Q0,Q1,Q2,…Qm}
Q0- Заключительное состояние, попав в
которое машина завершает работу
Q1- начальное состояние из которого машина
начинает работу

6.

Работа машины определяется
программой, состоящей из
команд вида:
QiAj QkAl
QiAj QkAl
QiAj QkAl

7.

Шаг машины заключается в том,
что:
Содержимое Aj стирается с ленты и на
его место записывается символ Al
Машина переходит в новое состояние
Qk
Машина переходит к обозрению
следующей ячейки справа, если ,
ячейки слева, если и остается на
месте, если

8.

Программы удобно писать в виде
таблицы
_
1
Q1
Q2
_ Q2 1 Q0
1 Q1 1 Q2
Преобразовать слово 1_1, если
обозревается крайний правый символ
слова

9.

Преобразовать слово _111_1111,
если обозревается крайний
левый символ
_
1
Q1
1 Q2
1 Q1
Q2
_ Q3
1 Q2
Q3
_ Q0