Построение машины тьюринга

Машина Тьюринга – абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

В состав машины Тьюринга входит ограниченная слева и бесконечная справа лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Условие МТ3:

M2
B1	0RB1	1SB0(1)
B2	1LB2	1SB0(2)

M4
D1	0RD2	1SD0(1)
D1	1LD1	1SD0(2)

M3
C1	1RC1	0RC2
C2	0SC0(1)	1SC0(2)

M4
A1	0RA1	0SA2
A2	0SA1	1RA2

MT3
B1	0LB1	1SB0(1)
B2	1LB2	1SBO(2)
D1	0RD2	1SD0(1)
D2	1LD1	1SD0(2)
C1	1RC1	0RC2
C2	0SC0(1)	1SC0(2)
A1	0RA1	0SA2
A2	0SC0	1RA2

MT3	MT3
B1	0RB1	1SD1	1RF2
B2	1LB2	1SC1	0SB1
D1	0RD2	1SD0	1SC1
D2	1LD1	1SD0	1SA1
C1	1RC1	0RC2	0RC2
C2	0SA1	1SB1	1SF1
A1	ORA1	0SA2	0SA2
A2	0SA1	1RA2	1RA2

Дата добавления: 2015-07-16