Тезис Клини — Поста¶

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

¶История

Тезис был сформулирован независимо двумя выдающимися логиками XX века: американским математиком Стивеном Коулом Клини (1909–1994) и польско-американским логиком Эмилем Постом (1897–1954). Работы обоих учёных относятся к 1930–1940-м годам, когда активно развивалась теория рекурсивных функций и теория алгоритмов.

Клини, будучи учеником Алонзо Чёрча, внёс значительный вклад в формализацию понятия вычислимости через частично-рекурсивные функции. В 1936 году он опубликовал работу, в которой показал, что множество истинных утверждений арифметики (в частности, арифметики Пеано) не является рекурсивно перечислимым. Однако в 1943 году он сформулировал более сильное утверждение: любое рекурсивно перечислимое множество может быть представлено как множество значений некоторой частично-рекурсивной функции, и, что более важно, любое множество, определимое в арифметике первого порядка, является рекурсивно перечислимым.

Пост, в свою очередь, в 1944 году опубликовал работу «Рекурсивно перечислимые множества натуральных чисел и их проблемы разрешимости», где независимо пришёл к аналогичным выводам. Он ввёл понятие «рекурсивно перечислимого множества» и доказал, что проблема остановки для машин Тьюринга (или, в его терминологии, проблема «принадлежности к множеству» для некоторого рекурсивно перечислимого множества) является алгоритмически неразрешимой. Пост также показал, что существует рекурсивно перечислимое множество, которое не является рекурсивным (то есть неразрешимым). Это открытие стало основой для формулировки тезиса.

¶Формулировка

Тезис Клини — Поста может быть сформулирован в нескольких эквивалентных вариантах:

¶Основная формулировка

Класс рекурсивно перечислимых множеств совпадает с классом множеств, определимых в формальной арифметике (арифметике первого порядка).

Более строго: множество натуральных чисел \( A \) является рекурсивно перечислимым тогда и только тогда, когда существует формула \( \phi(x) \) языка арифметики первого порядка (с кванторами по натуральным числам и операциями сложения, умножения, равенства, нуля и единицы) такая, что для любого натурального числа \( n \): \[ n \in A \iff \mathbb{N} \models \phi(n) \] где \( \mathbb{N} \) — стандартная модель натуральных чисел.

¶Следствие для неразрешимости

Из тезиса вытекает важное следствие: множество истинных арифметических утверждений (арифметическая истина) не является рекурсивно перечислимым. Это означает, что не существует алгоритма, который мог бы перечислить все истинные утверждения арифметики, не включая ложных. Более того, это множество является рекурсивно перечислимым лишь в том смысле, что оно может быть перечислено, но не может быть разрешено (то есть нельзя алгоритмически проверить, является ли данное утверждение истинным).

¶Связь с теоремой Гёделя о неполноте

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

¶Доказательство

Доказательство тезиса Клини — Поста опирается на две ключевые идеи:

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

1. Обратное направление: Любая формула арифметики первого порядка может быть преобразована в рекурсивно перечислимое множество. Для этого используется понятие «истинности» в стандартной модели: множество натуральных чисел, удовлетворяющих формуле, является рекурсивно перечислимым, поскольку можно алгоритмически перебирать все возможные значения переменных и проверять истинность формулы (хотя этот процесс может не завершаться для ложных утверждений).

Формально, доказательство использует теорему о представлении рекурсивно перечислимых множеств в арифметике: для любого рекурсивно перечислимого множества \( A \) существует формула \( \phi(x) \) такая, что \( n \in A \) тогда и только тогда, когда \( \phi(n) \) доказуема в арифметике Пеано. Обратно, любая формула \( \phi(x) \) определяет рекурсивно перечислимое множество, поскольку можно алгоритмически перебирать все доказательства в арифметике Пеано и проверять, доказуемо ли \( \phi(n) \) для данного \( n \).

¶Значение и следствия

¶В теории вычислимости

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

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

¶В математической логике

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

¶В философии математики

Тезис Клини — Поста имеет важные философские следствия. Он показывает, что существует принципиальное различие между «истинностью» и «доказуемостью» в математике. Истина не может быть полностью сведена к формальным доказательствам, поскольку множество истинных утверждений всегда «богаче» множества доказуемых. Это ставит под вопрос возможность полной формализации математического знания.

¶Критика и ограничения

Тезис Клини — Поста является математически строгим утверждением, доказанным в рамках стандартной теории множеств и теории вычислимости. Однако его интерпретация зависит от принятого определения «рекурсивно перечислимого» и «арифметически определимого». В частности:

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

¶Примеры

¶Пример 1: Множество чётных чисел

Множество чётных натуральных чисел является рекурсивно перечислимым (и даже рекурсивным). Оно определимо формулой арифметики: \( \exists y (x = 2 \cdot y) \). Согласно тезису, это множество является рекурсивно перечислимым, что очевидно.

¶Пример 2: Проблема остановки

Множество пар (код программы, входные данные), для которых программа останавливается, является рекурсивно перечислимым, но не рекурсивным. Оно определимо формулой арифметики, выражающей существование конечного числа шагов вычисления. Это классический пример, иллюстрирующий тезис.

¶Пример 3: Множество истинных утверждений арифметики

Множество всех истинных утверждений арифметики (в стандартной модели) является рекурсивно перечислимым, но не рекурсивным. Оно определимо формулой, выражающей «истинность» в арифметике, но эта формула не может быть выражена в самой арифметике первого порядка (теорема Тарского о неопределимости истины).

¶Источники

1. Kleene, S. C. (1943). Recursive predicates and quantifiers. Transactions of the American Mathematical Society, 53(1), 41–73.
2. Post, E. L. (1944). Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, 50(5), 284–316.
3. Rogers, H. (1967). Theory of Recursive Functions and Effective Computability. McGraw-Hill.
4. Boolos, G. S., Burgess, J. P., & Jeffrey, R. C. (2007). Computability and Logic (5th ed.). Cambridge University Press.
5. Odifreddi, P. (1989). Classical Recursion Theory. North-Holland.