Машина Тьюринга: определение

Машина Тьюринга — простейшая модель, которая, как считается, вычисляет всё вычислимое. Вся её сила — в бесконечной ленте.

Машина Тьюринга — конечный автомат с бесконечной лентой и головкой, которая читает и записывает символы и двигается влево/вправо.

Анатомия машины

Формально машина Тьюринга — семёрка, но суть в трёх частях. Лента — бесконечная в обе стороны последовательность ячеек, в каждой символ ленточного алфавита Γ (включая особый «пробел» ␣). Головка стоит над одной ячейкой: читает её символ и может записать новый. Управление — конечное множество состояний с функцией переходов δ: (состояние, прочитанный символ) → (новое состояние, символ для записи, движение L или R).

Ключевые отличия от автоматов: (1) головка двигается в обе стороны (не только вперёд по входу); (2) машина пишет на ленту, используя её как неограниченную память; (3) машина может не остановиться — зациклиться навсегда. Это последнее свойство и порождает неразрешимость.

лента:  … ⊔ ⊔ 1 0 1 1 ⊔ ⊔ …
                  ▲
               головка (читает '1', state=q)

переход δ(q, 1) = (q', 0, R):
  записать 0, перейти в q', сдвинуть головку вправо

Принятие и остановка

У машины есть особые состояния: q_accept (принять) и q_reject (отвергнуть). Попав в них, машина останавливается. На входе w машина может: принять (дойти до q_accept), отвергнуть (дойти до q_reject) или зациклиться (никогда не остановиться). Язык машины — множество принятых строк. Язык называют распознаваемым (рекурсивно-перечислимым), если машина принимает все его строки (на прочих может зацикливаться), и разрешимым (рекурсивным), если машина всегда останавливается с ответом да/нет. Это различие — сердце теории вычислимости.

Симуляция машины Тьюринга на Python

Реализуем универсальный симулятор и запустим машину, инвертирующую биты (0↔1) на ленте.

def run_tm(delta, start, accept, reject, tape, blank="_"):
    tape = list(tape)
    head, state, steps = 0, start, 0
    while state not in (accept, reject) and steps < 1000:
        if head < 0:
            tape.insert(0, blank); head = 0
        if head >= len(tape):
            tape.append(blank)
        sym = tape[head]
        if (state, sym) not in delta:
            state = reject; break
        state, write, move = delta[(state, sym)]
        tape[head] = write
        head += 1 if move == "R" else -1
        steps += 1
    return "".join(tape).strip(blank), state

# машина: инвертировать биты, дойдя до пробела — принять
delta = {
    ("q0", "0"): ("q0", "1", "R"),
    ("q0", "1"): ("q0", "0", "R"),
    ("q0", "_"): ("qa", "_", "R"),
}
result, final = run_tm(delta, "q0", "qa", "qr", "1011")
print("лента после:", result)
print("состояние:", final)

Вывод:

лента после: 0100
состояние: qa

Машина прошла по ленте «1011», инвертировав каждый бит в «0100», встретила пробел и приняла. Запись на ленту — то, чего не умели ни конечный, ни магазинный автоматы.

Как работает под капотом

Состояние всей машины в момент времени называют конфигурацией: содержимое ленты + позиция головки + текущее состояние. Вычисление — последовательность конфигураций, связанных переходами. Несмотря на примитивность (читать-писать-двигаться), машина Тьюринга вычисляет всё, что вычисляет современный компьютер: оперативная память моделируется лентой, регистры — состояниями. Более того, существует универсальная машина Тьюринга — она принимает на вход описание другой машины и её вход и симулирует её. Это прообраз идеи «программа как данные» и, по сути, теоретическая модель самого компьютера.

Частые ошибки

Считать, что машина всегда останавливается. Нет — зацикливание легально и принципиально важно: именно оно делает проблему остановки неразрешимой.

Путать распознаваемый и разрешимый. Разрешимый — машина всегда отвечает да/нет. Распознаваемый — принимает «да», но на «нет» может зациклиться. Разрешимые ⊂ распознаваемые.

Думать, что лента — это вход. Лента — рабочая память: машина пишет и стирает, выходя далеко за пределы входной строки.

Итог

Машина Тьюринга = конечное управление + бесконечная лента + головка, которая читает, пишет и двигается влево/вправо.
На входе машина принимает, отвергает или зацикливается; язык — множество принятых строк.
Разрешимый язык — машина всегда останавливается; распознаваемый — принимает «да», но может зациклиться на «нет».
Универсальная машина симулирует любую другую — теоретический прообраз компьютера и идеи «программа как данные».