Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита 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 в единичной системе:
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).
Достарыңызбен бөлісу: |