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



бет2/4
Дата07.04.2023
өлшемі17.58 Kb.
#471879
түріРеферат
1   2   3   4
Машина Тьюринга

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


Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации i, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

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


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

Набор правил

Набор правил

q0*→q0R

q4a→q4aR

q01→q0R

q4=→q4=R

q0×→q1×R

q41→q41R

q11→q2aR

q4*→q51R

q21→q21L

q5*→q2*L

q2a→q2aL

q6a→q61R

q2=→q2=L

q6×→q7×R

q2×→q3×L

q7a→q7aR

q31 → q4aR

q71→q2aR

q3a→q3aL

q7=→q8=L

q3*→q6*R

q8a→q81L

q4×→q4×R

q8×→q9H

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

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


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




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет