Что такое вычисление: от абака до Тьюринга и что значит «вычислимо»

Прежде чем говорить о битах, процессорах и веб-приложениях, стоит задать вопрос, который кажется наивным, но на самом деле лежит в фундаменте всей информатики: что вообще значит «вычислить» что-либо? Мы интуитивно понимаем, что сложить два числа — это вычисление, а «придумать хорошую мелодию» — вроде бы нет. Но где проходит граница? Есть ли задачи, которые невозможно решить никакой машиной, как бы быстро она ни работала и сколько бы памяти ни имела? Оказывается, да — и это не инженерное ограничение сегодняшнего дня, а математический факт, доказанный ещё до появления первого электронного компьютера.

Эта статья — фундамент всего трека. Мы не будем углубляться в детали; наша цель — построить точную интуицию: что такое вычисление, откуда взялось это понятие, почему ваш ноутбук, язык SQL с рекурсией и клеточный автомат «Жизнь» в глубоком смысле одинаково мощны, и почему у любой вычислительной машины есть непреодолимая стена.

Вычисление как механическое преодоление незнания

Начнём с определения, которое будем уточнять по ходу текста:

Вычисление — это преобразование входных символов в выходные по конечному набору чётких механических правил, где на каждом шаге правило выбирается однозначно и не требует «понимания», интуиции или творчества.

Ключевое слово здесь — механическое. Если процедуру можно выполнить, слепо следуя инструкции, не понимая смысла символов, — это вычисление. Столбиком умножить 347 на 89 может человек, который не знает, что такое число: достаточно помнить таблицу умножения и правило переноса. Именно эта «бессмысленность» и делает вычисление переносимым на машину. Машина не понимает — она следует правилам.

Стоит помнить исторический факт: слово computer до 1940-х годов означало человека — обычно женщину, — чьей профессией было выполнять арифметические расчёты по заданной процедуре. Расчёт баллистических таблиц, орбит комет, логарифмов — всё это делали «вычислители», механически применяя правила. Электронная машина не изобрела вычисление; она автоматизировала уже существовавшую человеческую деятельность.

Отсюда сразу следуют три свойства, которые останутся с нами до конца трека:

• Конечность правил. Инструкция должна умещаться в конечный текст. Бесконечная «таблица ответов на всё» — не вычисление, а жульничество.
• Дискретность шагов. Процесс разбит на отдельные элементарные операции, каждая из которых выполняется за конечное время.
• Детерминированность (в базовой модели). Из текущего состояния и входа следующий шаг определён однозначно.

Три тысячи лет инструментов: от абака до Бэббиджа

Идея переложить счёт на устройство очень старая. Но важно видеть, чем именно отличались вехи — где просто ускоряли человека, а где впервые появлялась идея программы.

Обратите внимание на перелом. Абак, Паскалина и арифмометр Лейбница — это инструменты: они выполняют одну фиксированную операцию, а последовательность операций держит в голове человек. Революция Жаккара в том, что поведение машины задаётся сменным носителем — перфокартой: та же машина ткёт другой узор, если сменить карты. Бэббидж переносит эту идею на вычисления: его так и не построенная целиком аналитическая машина уже имела всё, что мы сегодня зовём компьютером, — отдельную память, арифметическое устройство, условные переходы и циклы, управляемые перфокартами. А Ада Лавлейс первой поняла ключевое: если машина умеет обрабатывать символы по правилам, то числа — лишь частный случай, и такая машина в принципе могла бы работать с музыкой, текстом, логикой. Это и есть зерно идеи универсальности, к которой мы сейчас придём.

Подробнее про то, как из этих идей выросла реальная архитектура железа, — в статье https://courses.digitable.life/post/computer-science/05-how-cpu-works/ про устройство процессора.

Кризис оснований: почему математикам понадобилось определить «алгоритм»

Парадоксально, но строгое понятие вычисления родилось не из инженерии, а из чистой математики — и из её кризиса. В начале XX века Давид Гильберт сформулировал программу: свести всю математику к формальной системе аксиом и правил вывода, а затем механически проверять любое утверждение. Кульминацией была Entscheidungsproblem (проблема разрешимости, 1928): существует ли общая механическая процедура, которая для любого математического утверждения выдаёт «истинно» или «ложно»?

Чтобы честно ответить «нет, такой процедуры не существует», нужно было сначала точно определить, что такое механическая процедура вообще. Нельзя доказать, что чего-то нельзя сделать никаким алгоритмом, пока слово «алгоритм» остаётся расплывчатым. И в середине 1930-х сразу несколько математиков независимо предложили строгие определения:

• Алонзо Чёрч — лямбда-исчисление (1936): вычисление как подстановка и упрощение функций.
• Алан Тьюринг — машина Тьюринга (1936): вычисление как работа абстрактного устройства с лентой.
• Курт Гёдель и Стивен Клини — общерекурсивные функции: вычисление как построение функций из простых базовых операций, композиции и рекурсии.
• Эмиль Пост — независимо, модель, очень близкая к машине Тьюринга.

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

Про лямбда-исчисление — тот самый подход Чёрча, из которого выросло функциональное программирование, — есть отдельный глубокий трек: https://courses.digitable.life/post/lambda-calculus/00-overview/. А формальную сторону автоматов и разрешимости мы ещё раз затронем в https://courses.digitable.life/post/computer-science/15-theory-of-computation/.

Машина Тьюринга: минимальная модель, которая может всё

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

Машина Тьюринга состоит всего из четырёх частей:

1. Лента — бесконечная в обе стороны полоса, разбитая на ячейки. В каждой ячейке — один символ из конечного алфавита (например, 0, 1 и пустой символ ␣). Это одновременно и вход, и память, и выход.
2. Головка — читает символ в текущей ячейке и может записать в неё новый, затем сдвинуться на одну ячейку влево или вправо.
3. Конечное множество состояний — «настроение» машины. В каждый момент она находится ровно в одном состоянии.
4. Таблица переходов — конечный набор правил вида: «если состояние S и под головкой символ X — запиши символ Y, сдвинься влево/вправо и перейди в состояние S′». Это и есть программа машины.

Вся мощь спрятана в таблице переходов. Разберём конкретную машину, которая прибавляет единицу к двоичному числу. Пусть на ленте записано число, головка стоит на его старшем разряде. Алгоритм человека очевиден: дойти до младшего разряда справа, а потом идти влево, обрабатывая перенос. Ровно это и кодируют состояния:

• SEEK — едем вправо до конца числа (до пустой ячейки);
• ADD — идём влево, разбираясь с переносом: 0 превращаем в 1 и останавливаемся; 1 превращаем в 0 и тащим перенос дальше влево; если число всё из единиц — дописываем 1 в новую старшую ячейку.

Каждая стрелка читается как «читаемый символ → записываемый символ, сдвиг». Это буквально вся программа: пять правил. И заметьте — здесь уже есть всё, что вы встретите в реальном коде: цикл (петля SEEK → SEEK), условие (развилка в ADD), завершение (HALT). Более того, есть и скрытый нюанс: попадёт ли машина когда-нибудь в HALT? Для этой конкретной программы — да, всегда. Но в общем случае, как мы увидим, ответить на такой вопрос механически невозможно.

Универсальная машина Тьюринга. Тьюринг сделал ещё один решающий шаг. Раз программа машины — это конечная таблица, её саму можно закодировать символами и положить на ленту. Тогда существует одна машина U, которая принимает на вход описание любой другой машины M вместе с её входом и в точности воспроизводит поведение M. U — это универсальная машина Тьюринга, и это прямая математическая модель того, что делает ваш компьютер: процессор — фиксированное «железо», которое исполняет произвольную программу, поданную ему как данные. Идея «программа хранится в памяти как обычные данные» — это и есть архитектура фон Неймана из статьи https://courses.digitable.life/post/computer-science/05-how-cpu-works/.

Тезис Чёрча — Тьюринга: все дороги ведут в одно место

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

Обобщение этого опыта называется тезисом Чёрча — Тьюринга:

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

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

Отсюда важнейшее практическое понятие — тьюринг-полнота. Систему называют тьюринг-полной, если на ней можно запрограммировать любую машину Тьюринга (то есть вычислить любую вычислимую функцию). И тьюринг-полнота обнаруживается в самых неожиданных местах:

• Python, Go, C — очевидно, тьюринг-полны.
• Клеточный автомат «Жизнь» Конвея — набор из четырёх правил про живые и мёртвые клетки — тьюринг-полон: внутри него строят логические вентили и целые процессоры.
• Система типов C++ и шаблоны — тьюринг-полны, поэтому компилятор в принципе может зациклиться на этапе проверки типов.
• SQL с рекурсивными CTE, таблица Excel с формулами, даже игра Minecraft с редстоуном — всё это тьюринг-полно.

Практический вывод: как только вы даёте пользователю «немножко программируемости» (шаблоны, правила, макросы), вы рискуете нечаянно получить тьюринг-полный язык — со всеми его проблемами, включая ту, к которой мы переходим.

Стена: чего нельзя вычислить в принципе

Здесь наивная интуиция даёт трещину. Кажется, что при достаточных ресурсах вычислить можно всё. Это неверно, и доказать это можно двумя способами — счётным аргументом и знаменитой проблемой остановки.

Считаем: программ мало, функций много

Сколько существует программ? Программа — это конечная строка символов из конечного алфавита $\Sigma$. Множество всех конечных строк $\Sigma^{\ast}$ счётно: их можно занумеровать натуральными числами (сначала все строки длины 1, потом длины 2 и так далее). Значит, вычислимых функций не больше, чем натуральных чисел:

$$|\text{программы}| = |\Sigma^{\ast}| = \aleph_0$$

А сколько существует функций вида $f: \mathbb{N} \to \lbrace 0, 1 \rbrace$? По теореме Кантора их несчётно много:

$$|\lbrace f: \mathbb{N} \to \lbrace 0, 1 \rbrace \rbrace| = 2^{\aleph_0} > \aleph_0$$

Функций несоизмеримо больше, чем программ. Значит, почти каждая функция невычислима: для подавляющего большинства функций просто не существует программы, которая бы их считала. Вычислимые функции — исчезающе редкий, хоть и самый интересный, островок в океане всех функций. Именно это и рисует карта ниже.

Проблема остановки: конкретный невычислимый вопрос

Счётный аргумент говорит, что невычислимые функции существуют, но не даёт «пощупать» ни одну. Тьюринг дал конкретную. Вопрос предельно практичный:

Проблема остановки. Существует ли программа halts(P, x), которая по тексту любой программы P и любому входу x за конечное время правильно отвечает, остановится ли P на входе x или зациклится навсегда?

Такая штука была бы бесценна: антивирус, который заранее знает, зависнет ли код; компилятор, гарантирующий отсутствие бесконечных циклов. Тьюринг доказал, что halts не существует. Доказательство — самореференция, тот же приём, что у парадокса лжеца. Предположим, halts есть, и построим на её основе вредную программу paradox:

def halts(program, inp):
    # ГИПОТЕТИЧЕСКИ: возвращает True, если program(inp) когда-нибудь остановится,
    # и False, если program(inp) зациклится. Работает для любых аргументов.
    ...

def paradox(program):
    if halts(program, program):   # спрашиваем: остановится ли program, поданная сама себе?
        while True:               # если ДА — намеренно зацикливаемся навсегда
            pass
    else:
        return                    # если НЕТ — тут же останавливаемся

Теперь зададим коварный вопрос: что делает paradox(paradox)? Разберём по логике:

В любом варианте halts ошибается на программе paradox. Раз никакая корректная halts не может дать верный ответ хотя бы на одном входе, значит универсальной программы halts не существует. Проблема остановки неразрешима — это первый и самый знаменитый пример вопроса, на который нельзя ответить никаким алгоритмом.

Хуже того, теорема Райса обобщает это: любое нетривиальное свойство поведения программ (а не её текста) неразрешимо в общем случае. «Вычисляет ли эта программа всегда правильный результат?», «эквивалентны ли две программы?», «есть ли в этом коде вирусное поведение?» — все эти вопросы в общем виде невычислимы.

Где эта теория «протекает» в реальную инженерию

Может показаться, что бесконечная лента и парадоксальные программы — забавы для математиков. На деле граница вычислимости — это не абстракция, а стена, о которую регулярно бьётся практика.

• Идеальный статический анализатор невозможен. Линтеры, типизаторы и антивирусы не могут точно определить, зациклится ли код, есть ли гонка данных или уязвимость. Это прямое следствие теоремы Райса. Поэтому реальные инструменты выбирают одно из двух: быть консервативными (иногда ложно ругаться на корректный код) или неполными (иногда пропускать проблему). «Идеального» третьего варианта не существует — и это доказано.
• Компилятор может зависнуть. Раз система типов C++ или Rust тьюринг-полна, проверка типов в принципе может не завершиться. Поэтому компиляторы вводят искусственные ограничения — лимит глубины рекурсии шаблонов, — жертвуя полнотой ради гарантии остановки.
• Осторожнее с «чуть-чуть программируемостью». Добавляя в продукт язык шаблонов, движок правил или конфигурацию с условиями, легко нечаянно сделать её тьюринг-полной. Тогда «проверить конфиг на корректность перед деплоем» становится в общем случае неразрешимой задачей. Часто правильнее сознательно оставить язык не тьюринг-полным (без произвольных циклов) — тогда про него можно доказывать свойства.
• Реальная машина — не машина Тьюринга. У вашего компьютера память конечна, а у машины Тьюринга лента бесконечна. Формально любой реальный компьютер — это конечный автомат с огромным, но конечным числом состояний. Обычно этой разницей можно пренебречь, но она напоминает: абстракция «бесконечной памяти» — идеализация, и она протекает ровно тогда, когда программа упирается в реальный предел RAM или диска (см. https://courses.digitable.life/post/computer-science/06-memory-hierarchy/).

Вычислимо ≠ осуществимо: намёк на сложность

И последнее принципиальное разграничение. Тьюринг ответил на вопрос «можно ли вычислить в принципе?». Но у инженера есть второй, не менее важный вопрос: «можно ли вычислить за разумное время?». Это разные вопросы.

Задача коммивояжёра, факторизация больших чисел, выполнимость булевых формул (SAT) — все они вычислимы: алгоритм существует. Но известные алгоритмы для них растут экспоненциально, и для входа в пару сотен элементов «решение» потребовало бы времени больше возраста Вселенной. Формально задача решена, практически — нет. На карте выше это средний слой: вычислимые, но лежащие вне класса практически осуществимых (P).

Именно этот разрыв изучает теория сложности, а на криптографии — например, на предполагаемой трудности факторизации — держится вся современная безопасность в интернете. Интуицию Big-O и различие «легко/трудно» мы разбираем в https://courses.digitable.life/post/computer-science/10-algorithms-and-complexity/, а глубоко — в отдельном треке https://courses.digitable.life/post/algorithms/00-overview/.

Мини-итог

• Вычисление — механическое преобразование символов по конечному набору однозначных правил; «понимание» не требуется, и именно поэтому его можно поручить машине.
• История шла от инструментов (абак, арифмометр) к идее программы на сменном носителе (Жаккар, Бэббидж, Лавлейс) и, наконец, к формальной модели вычисления как такового.
• Машина Тьюринга (лента, головка, состояния, таблица переходов) — минимальная модель, которая умеет всё, что умеет любой компьютер. Универсальная машина Тьюринга — прообраз идеи «программа как данные».
• Тезис Чёрча — Тьюринга: все разумные модели вычисления равномощны. Отсюда — понятие тьюринг-полноты, которое всплывает даже в шаблонах, таблицах и системах типов.
• Есть абсолютная граница: функций несоизмеримо больше, чем программ, поэтому почти всё невычислимо; а проблема остановки — конкретный вопрос, на который не ответит никакой алгоритм.
• Эта граница реальна: она объясняет, почему нет идеального анализатора кода, почему компилятор может зависнуть и почему «вычислимо» не значит «осуществимо».

Источники

• A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem (1936) — оригинальная работа: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
• Michael Sipser. Introduction to the Theory of Computation — стандартный учебник по вычислимости и сложности.
• Charles Petzold. The Annotated Turing — построчный разбор статьи Тьюринга для широкой аудитории.
• Stanford Encyclopedia of Philosophy, The Church-Turing Thesis: https://plato.stanford.edu/entries/church-turing/

Что дальше

Мы выяснили, что вычисление — это преобразование символов по правилам. Следующий вопрос: а какими бывают эти символы на самом деле? Как получается, что числа, текст, картинки и звук — всё внутри машины оказывается одним и тем же? Ответ начинается с двух знаков — нуля и единицы.

Двоичная система, биты и байты: как всё становится числами