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

жүктеу/скачать 17.58 Kb.

бет	2/4
Дата	07.04.2023
өлшемі	17.58 Kb.
	#471879
түрі	Реферат

1 2 3 4

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

3. Пример машины Тьюринга

2. Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации i, a_j> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

3. Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Набор правил	Набор правил
q₀*→q₀R	q₄a→q₄aR
q₀1→q₀R	q₄=→q₄=R
q₀×→q₁×R	q₄1→q₄1R
q₁1→q₂aR	q₄*→q₅1R
q₂1→q₂1L	q₅→q₂L
q₂a→q₂aL	q₆a→q₆1R
q₂=→q₂=L	q₆×→q₇×R
q₂×→q₃×L	q₇a→q₇aR
q₃1 → q₄aR	q₇1→q₂aR
q₃a→q₃aL	q₇=→q₈=L
q₃→q₆R	q₈a→q₈1L
q₄×→q₄×R	q₈×→q₉H

Умножим с помощью МТ 3 на 2 в единичной системе:

В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).

жүктеу/скачать 17.58 Kb.

Достарыңызбен бөлісу:

1 2 3 4