Тезис Чёрча-Тьюринга

Что вообще значит слово «вычислимо»? Тезис Чёрча-Тьюринга даёт ответ: вычислимо всё, что может машина Тьюринга — и ничего сверх.

Тезис Чёрча-Тьюринга: всякая функция, вычислимая любым разумным алгоритмическим способом, вычислима машиной Тьюринга.

Проблема определения «алгоритма»

До 1930-х «алгоритм» был интуитивным понятием: «механическая процедура из конечных шагов». Но чтобы доказывать неразрешимость, нужно точное определение — иначе как утверждать, что задачи не решает ни один алгоритм? В 1936 году несколько математиков независимо формализовали вычислимость: Алонзо Чёрч через λ-исчисление, Алан Тьюринг через свои машины, Гёдель и Клини через рекурсивные функции. И тут случилось чудо.

Удивительное совпадение

Все эти совершенно разные формализмы оказались эквивалентны: они вычисляют ровно один и тот же класс функций. λ-исчисление = машины Тьюринга = рекурсивные функции = и позже добавленные клеточные автоматы, машины с регистрами, языки программирования. Это устойчивое совпадение — сильнейший аргумент, что мы ухватили правильное, объективное понятие вычислимости.

разные модели — один класс вычислимых функций:

  машина Тьюринга  ≡  λ-исчисление (Чёрч)
         ≡  рекурсивные функции (Гёдель-Клини)
         ≡  машины с регистрами
         ≡  любой Тьюринг-полный язык (Python, C, …)

все вычисляют РОВНО одно и то же множество функций

Тезис — не теорема

Важнейший нюанс: тезис Чёрча-Тьюринга нельзя доказать. Он связывает интуитивное понятие («то, что вычислимо хоть как-то») с формальным (машина Тьюринга). Интуитивное понятие не определено математически, поэтому равенство недоказуемо в строгом смысле — это гипотеза о природе вычислений. Но за 90 лет не нашли ни одного контрпримера: никакая модель (включая квантовые компьютеры) не вычислила функцию, недоступную машине Тьюринга. Квантовый компьютер быстрее на некоторых задачах, но класс вычислимого тот же.

Тьюринг-полнота на практике

Язык называют Тьюринг-полным, если он может симулировать любую машину Тьюринга. Практически все языки программирования таковы. Покажем игрушечную «машину с регистрами» (всего три операции: inc, dec, jump-if-zero) — этого минимума уже достаточно для Тьюринг-полноты. Сложим два числа.

# минималистичная регистровая машина: inc r, dec r, jz r label
def run(program, regs):
    pc = 0
    while 0 <= pc < len(program):
        op = program[pc]
        if op[0] == "inc":
            regs[op[1]] += 1; pc += 1
        elif op[0] == "dec":
            regs[op[1]] -= 1; pc += 1
        elif op[0] == "jz":               # если регистр 0 — прыжок
            pc = op[2] if regs[op[1]] == 0 else pc + 1
        else:
            break
    return regs

# сложение: r0 += r1 (переливаем r1 в r0)
program = [
    ("jz", "r1", 4),   # 0: если r1==0 — конец
    ("dec", "r1"),     # 1: r1 -= 1
    ("inc", "r0"),     # 2: r0 += 1
    ("jz", "zero", 0), # 3: безусловный переход к 0 (zero всегда 0)
]
result = run(program, {"r0": 5, "r1": 3, "zero": 0})
print("5 + 3 =", result["r0"])

Вывод:

5 + 3 = 8

Три примитивные операции уже Тьюринг-полны: на них можно построить что угодно вычислимое. Это и есть практическая сторона тезиса — простейший набор команд достигает полной вычислительной мощи.

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

Тезис объясняет, почему все языки «одинаково мощны»: Python не вычисляет ничего, что недоступно ассемблеру, а ассемблер — ничего сверх машины Тьюринга. Различия — в удобстве, скорости, выразительности, но не в классе разрешимых задач. Поэтому, доказав неразрешимость на машине Тьюринга, мы автоматически получаем неразрешимость для любого языка. Проблема остановки неразрешима не только для машин Тьюринга, но и для программ на Python, Java, чём угодно Тьюринг-полном.

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

Считать тезис доказанной теоремой. Это гипотеза, связывающая интуицию с формализмом; доказать её нельзя, но контрпримеров нет.

Думать, что квантовые компьютеры нарушают тезис. Они меняют сложность (скорость), но не вычислимость: класс разрешимых задач тот же.

Путать «Тьюринг-полный» и «практичный». Brainfuck и игра «Жизнь» Тьюринг-полны, но писать на них больно; полнота — про мощность, не про удобство.

Итог

• Тезис Чёрча-Тьюринга: вычислимое = вычислимое машиной Тьюринга; это определение «алгоритма».
• Разные модели (λ-исчисление, рекурсивные функции, машины Тьюринга) эквивалентны — сильный аргумент за тезис.
• Тезис недоказуем (связывает интуицию с формализмом), но за 90 лет без контрпримеров; квантовые машины его не нарушают.
• Все Тьюринг-полные языки равны по вычислимости; неразрешимость на МТ переносится на любой из них.