Вычислимые и невычислимые функции

Тьюринг в 1936 году доказал кое-что неудобное. Существуют задачи, которые невозможно решить алгоритмически - в принципе, не из-за нехватки мощности. ChatGPT не может определить, зациклится ли произвольная программа. Ни один LLM не сможет - никогда. Это не технологическое ограничение. Это математический запрет, доказанный строже, чем теорема Пифагора. IDE не может гарантировать отсутствие infinite loop. Type checker не может проверить все инварианты. Rust borrow checker намеренно консервативен - потому что точный анализ неразрешим. Это и есть тема урока.

• **IDE и статический анализ:** VS Code, IntelliJ, Pylance - все они консервативны и пропускают реальные баги, потому что точный анализ произвольного кода неразрешим. Это не недоработка - это математический потолок
• **Антивирусы:** VirusTotal, Kaspersky, Windows Defender работают через сигнатуры и эвристику - но универсального детектора произвольного вредоносного кода не существует и не может. Теорема Райса запрещает
• **Формальная верификация:** Amazon использует TLA+, AWS S3 верифицирован через Coq - но только для конечных, специфически описанных систем. Верифицировать произвольную программу невозможно в принципе

Вычислимые функции

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

**Вычислимая функция** (computable function) - это функция f: N → N, для которой существует алгоритм (программа, машина Тьюринга), способный для любого входа x за конечное число шагов вычислить f(x).

Ключевое слово - **алгоритм**. Точная последовательность шагов, которую можно записать на любом языке программирования. Python, Haskell, ассемблер - без разницы. По тезису Чёрча-Тьюринга, все достаточно мощные языки вычисляют один и тот же класс функций.

Следствие: если задача нерешаема на Python - нерешаема нигде. Ни на каком компьютере будущего, ни на квантовом. Пределы вычислимости - **математические**, а не технологические. Это важнейшее разграничение в теоретической информатике.

Тотальные функции

Не все функции одинаково «надёжны». **Тотальная функция** определена для каждого входа - она всегда даёт ответ и всегда завершается. В системах реального времени (RTOS, авиационное ПО, медицинские устройства) допустимы только тотальные функции: зависание равно катастрофе.

**Тотальная вычислимая функция** - это вычислимая функция f, которая определена для **всех** натуральных чисел. Программа, вычисляющая f, завершается на любом входе.

**Проблема Коллатца** - пример на стыке: мы **верим**, что функция тотальна (т.е. всегда доходит до 1), но математически это не доказано. Для некоторых n программа может работать бесконечно - мы просто этого не знаем.

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

Частичные функции

**Программа работает уже час.** Запущена ночью, утром всё ещё крутится. Зависла навсегда или вот-вот выдаст результат? Если программа не даёт ответа на некоторых входах - она вычисляет **частичную функцию**. Большинство реальных программ частичны: интерпретаторы, серверы, поисковые алгоритмы.

**Частично вычислимая функция** (partial computable function) - функция, для которой существует алгоритм, но он может не завершиться на некоторых входах. Функция «определена» только там, где алгоритм останавливается.

Принципиальная **асимметрия**: если программа выдала ответ - результат достоверен. Но если программа работает - нет способа узнать, зависла ли она или ещё считает. Это не вопрос отладки. Это фундаментальный факт о вычислениях.

Программы можно пронумеровать - их **счётное** множество (как натуральные числа). Функций N → N - **несчётно** (как вещественных чисел). Между этими мощностями - пропасть. Подавляющее большинство математических функций не только не вычислены - они принципиально невычислимы.

Невычислимость и проблема остановки

Тьюрингу было 23 года. Компьютер ещё не был построен. И он доказал, что **существуют задачи, которые ни один компьютер не решит никогда** - не из-за нехватки мощности, а потому что это математически невозможно. Доказательство умещается в 20 строк кода и опирается на один изящный трюк.

**Проблема остановки** (Halting Problem): дана программа P и вход x. Определить, завершится ли P(x) за конечное время или будет работать бесконечно. Алан Тьюринг доказал в 1936 году, что эта задача **неразрешима** - не существует алгоритма, решающего её для всех пар (P, x).

Доказательство - элегантный приём **диагонализации** (от противного). Допустим, такой алгоритм HALTS(P, x) существует. Построим на его основе парадокс:

Последствия мгновенны и конкретны. IDE не может надёжно найти все infinite loops. Компилятор не может гарантировать отсутствие deadlocks в произвольной программе. Статический анализатор пропускает баги - не из-за недоработки, а потому что точный анализ сводится к проблеме остановки. Теорема Райса (1953) формализует это: любое непрямолинейное свойство программы по её поведению - неразрешимо.

Главный поворот: вычислимость - это исключение, а не правило. Программ счётно, функций N → N несчётно - разрыв как между натуральными и вещественными числами. Весь арсенал алгоритмов, языков, архитектур - это крошечный остров в океане невычислимого. Тьюринг описал его границы раньше, чем был построен первый компьютер.

Ключевые идеи

• **Вычислимость - не вопрос мощности:** если задача неразрешима на машине Тьюринга - квантовый компьютер, AGI и суперкомпьютер будущего её тоже не решат. Это математический барьер, не инженерный
• **Тотальные vs частичные:** тотальная функция гарантирует ответ на любом входе; частичная может зависнуть - и нет алгоритма, который отличит одно от другого для произвольной программы
• **Проблема остановки - центр всего:** доказательство Тьюринга через диагонализацию - шаблон для сотен других доказательств неразрешимости. От неё сводятся: эквивалентность программ, наличие багов, тотальность
• **Невычислимость - норма, вычислимость - исключение:** программ счётно, функций N → N несчётно. Почти все математические объекты не поддаются алгоритмической обработке - мы просто никогда с ними не встречаемся

Связанные темы

Вычислимость - фундамент, на котором строится вся теоретическая информатика:

• Машина Тьюринга — Формальная модель, через которую определяется вычислимость
• Рекурсивные и RE языки — Классификация языков по вычислимости - следующий уровень теории
• Формальные языки — Связь между грамматиками, автоматами и вычислимостью

Вопросы для размышления

• Если бы проблема остановки была разрешима - какие инструменты программирования стали бы возможны?
• Почему невозможность создания «универсального отладчика» не мешает нам создавать полезные (но неидеальные) инструменты анализа кода?
• Как аргумент о счётности программ и несчётности функций связан с диагональным аргументом Кантора о вещественных числах?

Связанные уроки

• fl-01-intro — Рекурсивно перечислимые языки (тип 0) - это языки, распознаваемые машинами Тьюринга
• cplx-01 — Вычислимость - необходимое условие для теории сложности: сначала можно ли, затем насколько быстро
• aut-01-fsm — Машина Тьюринга = конечный автомат + бесконечная лента; формально более мощная модель
• dm-01 — Диагонализация Кантора и доказательство неразрешимости - один и тот же метод самореференции
• fl-18-turing-machine