В каком смысле число «существует», если доказано, что оно невычислимо?

Отвечая на ваши три математических/экзистенциальных вопроса по порядку:

• Да. Существует ТМ, которая при запуске на пустой ленте в конце концов останавливается (через конечное число шагов) с точным десятичным разложением$x=\Sigma\left(10^{100},10^{100}\right)$на ленте. То же самое верно для$x\bmod 4$или$x^x$ или любое другое натуральное число .
• Не существует натурального числа, «которое нельзя вычислить за какое-либо конечное время».
• Для натуральных чисел такой проблемы нет.

С другой стороны, доказуемость — это еще одна проблема: не существует натурального числа.$n$так что ZFC доказывает $\ BB(7918)=n,$а совсем недавно у нас это для любого$m\ge 748,$нет натурального числа$n$так что ZFC доказывает$BB(m)=n.$(Здесь$BB$является функцией Busy Beaver по количеству шагов, предпринятых до остановки.)

NB : Поскольку ваши вопросы (и все ваше вступление), казалось, были о натуральных числах , это контекст моих ответов выше. Ситуация совершенно иная в более широком контексте действительных чисел . Обратите внимание, что каждое натуральное число имеет конечное представление, что является основной причиной его вычислимости. Напротив, действительное число обычно требует бесконечного представления, что открывает возможность того, что оно не поддается вычислению. (Оказывается, почти все действительные числа невычислимы.)

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

Теорема. Каждое натуральное число вычислимо.

Доказательство. Мы должны показать, что для каждого натурального числа$n$, существует машина Тьюринга, выход которой является, скажем, унарным представлением$n$. Будем действовать по индукции. Конечно, существует машина Тьюринга, выход которой пуст, т. е. представление$0$. Если у нас есть машина Тьюринга, вывод которой является унарным представлением$n$ясно, что мы можем модифицировать его, чтобы выводить еще одну единицу, чтобы получить унарное представление$n + 1$. Следовательно, каждое натуральное число действительно вычислимо. ◼

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

Чтобы сказать что-нибудь математически строгое о натуральных числах в интенсионале, мы должны сначала выбрать математическую модель для «описания натуральных чисел». К сожалению, канонического выбора нет, и разные варианты имеют разную выразительную силу. Если вы решите определить «описание натурального числа» как «машину Тьюринга, которая его вычисляет», то тавтологически каждое натуральное число в интенсионале вычислимо. Но вы также можете определить его как «формула$\phi$на языке теории множеств хотя бы с одной свободной переменной$n$так что ZFC доказывает$\exists ! n \in \mathbb{N} . \phi$". В этом случае верно, что не всякое натуральное число в интенсионале вычислимо - или, другими словами, нет процедуры (вычислимой или иной!), которая преобразовала бы формулу$\phi$в машину Тьюринга, которая (доказывает ZFC) вычисляет уникальное натуральное число, которое$\phi$описывает.

Я думаю, что этот набор вопросов и направлений исследования является одним из самых интересных в философии и основах математики! Сначала я отвечу на ваш последний вопрос: существует множество систем математики, которые разными способами пытаются решить вопрос о допущении существования только вычислимых объектов. Хорошим примером является подсистема арифметики второго порядка.$RCA_0$, что означает аксиому рекурсивного понимания. Этот набор аксиом намного слабее, чем, скажем, арифметика Пеано, и является одной из попыток уловить понятие «вычислимой арифметики». С вычислительной точки зрения он обладает многими замечательными свойствами, такими как тот факт, что любое множество, существование которого можно доказать в$RCA_0$имеет компьютерную программу проверки членства, и действительно, такая программа может быть более или менее механически реконструирована из доказательства существования (это более или менее переписка Карри-Ховарда, см. Википедию и этот фрагмент Wikibooks Haskell для получения дополнительной информации).

Вы также можете выполнить подмножество повседневной математики в$RCA_0$, такие как доказательство теоремы о промежуточном значении, существования алгебраических замыканий полей, теоремы Гёделя о правильности для логики первого порядка и (слабой версии) теоремы о полноте для того же самого. Однако оказывается, что многие интересные математические утверждения неверны.$RCA_0$, например, это не тот случай, когда каждая ограниченная возрастающая последовательность действительных чисел имеет верхнюю границу — именно потому, что существуют вычислимые последовательности действительных чисел, верхняя граница которых невычислима! Одним из примеров такой последовательности является последовательность нижних границ вероятности остановки Чайтина . В результате, занимаясь математикой в$RCA_0$во многих отношениях не очень хорош, или, по крайней мере, это совсем другой математический мир, чем тот, к которому привыкли самые чистые математики.

Подробнее о$RCA_0$, см., например, «Подсистемы арифметики второго порядка» Стивена Г. Симпсона. Проект вычислимых оснований математики для различных определений слова «вычислимый» является широкомасштабным, слишком большим, чтобы включить в него все, что имеет отношение к делу. Ключевые слова, которые могут быть здесь полезны, включают «конструктивизм», например, «Основы конструктивного анализа Бишопа», «рекурсивный анализ» и «рекурсивные контрпримеры», а также теорию зависимых типов, которая используется в языках программирования Idris и LEAN.

Что касается вашего второго вопроса, да, связь между утверждениями, которые не зависят от набора аксиом, и числами, которые невозможно вычислить, сильна как интуитивно, так и формально. Классический пример утверждения, независимого, скажем, от ZFC, состоит в том, что ZFC непротиворечив, что мы будем обозначать как$Con(ZFC)$. Но$Con(ZFC)$эквивалентно утверждению о конкретной компьютерной программе: «компьютерная программа, которая просматривает все доказательства в ZFC и останавливается при обнаружении противоречия, не останавливается». Это, в свою очередь, связано (среди прочих невычислимых функций) с функцией занятого бобра. В частности, предположим, что «компьютерная программа, которая просматривает все доказательства в ZFC и останавливается, обнаружив противоречие», является машиной Тьюринга с$X$состояния. Тогда любое предложение о ценности$\Sigma(X)$подразумевает либо$Con(ZFC)$или$\neg Con(ZFC)$, но, как мы знаем, ZFC не доказывает ни одно из этих утверждений, ZFC не может доказать$\Sigma(X)$равно некоторой конкретной конечной величине.

Здесь есть тонкость, на которую частично отвечает ответ res : ZFC действительно доказывает поверхностно связанное утверждение «существует некоторая машина Тьюринга, которая выводит$\Sigma(X)$». Но это в каком-то смысле тривиально, потому что ZFC доказывает утверждения «существует машина Тьюринга, которая выдает 1» и «существует машина Тьюринга, которая выдает 2» и так далее, что позволяет доказать «для всех натуральных чисел$n$, существует токарный станок, производящий n”. В сочетании с также тривиальным утверждением «$\Sigma(X)$— натуральное число», мы, конечно, получаем, что «существует некоторая машина Тьюринга, которая выдает$\Sigma(X)$”, но теперь можно увидеть, что это предложение не передает того, что может показаться означающим. Мы не просто хотим знать, какая из машин Тьюринга в мире выводит искомое число, мы хотим знать, какая из них, и здесь ZFC не может нам помочь. В самом деле, любая система аксиом, которая рекурсивно перечислима (существует компьютерная программа, которая напечатает весь, возможно, бесконечный набор аксиом), в конечном итоге не будет доказана.$\Sigma(Y)$для достаточно большого Y, по тому же рассуждению, что и выше.

Доказательство Адама Йедидии и Скотта Ааронсона о том, что значение Y в ZFC не превышает 8000 (позже уменьшено до 748), см. в статье A Relatively Small Turing Machine, поведение которой не зависит от теории множеств, а также в блоге Ааронсона об этом . Дополнительную информацию о функции занятого бобра и о том, как она связана с основами математики, см. в книге Ааронсона The Busy Beaver Frontier .

Я оставил ваш первый вопрос последним, потому что он в каком-то смысле самый острый и философский. Например, безусловно верно, что ZFC (да и PA, и другие достаточно слабые математические системы) доказывают утверждение

Разные люди по-разному реагируют на этот философский момент. Например, вся область конструктивной математики в значительной степени основывается на том, что «у нас не должно быть чисел и, в более общем смысле, математических объектов, существование которых доказано, но которые на самом деле не построены», для различных формализаций того, что именно означает «построен». С другой стороны, большинство математиков либо не думали об этом, либо не беспокоились об этом слишком сильно, либо признавали, что работают с объектами, которые (иногда) фундаментально отличаются от тех, которые поддаются вычислению. Две причины думать, что последняя идея не слишком сумасшедшая: во-первых, математика всегда связана с выяснением неизвестных вещей. Если бы я определил число$Q$с помощью$Q = 1$если$P \not= NP$еще$Q = 0$, то у нас также нет хорошего способа доказать, что значение$Q$есть, хотя большинство математиков считают, что ZFC доказывает, что$Q=1$, и, конечно же, значение$Q$не является независимым от ZFC. Во-вторых, это более нечетко, но большая часть математики опирается на объекты, которые, по крайней мере, интуитивно не поддаются вычислению, например, действительные числа. Идея континуума действительных чисел, простирающегося бесконечно далеко в обоих направлениях и не имеющего «промежутков», в некотором смысле очень интуитивна и не очень хорошо согласуется с моим представлением о том, с чем на самом деле может справиться компьютер. ! Вы можете кодировать действительные числа как последовательности Коши, (некоторые из которых) могут быть представлены в виде конечных компьютерных программ, но я, конечно, не думаю большую часть времени о какой-то компьютерной программе, перетасовывающей (конечные представления) последовательностей Коши, когда я думаю о таких теоремах, как «Всякая монотонно возрастающая последовательность действительных чисел имеет наименьшую верхнюю границу».

Наконец, хотя этот ответ уже стал очень длинным, он, вероятно, не был бы полным без хотя бы небольшого упоминания еще одного философского момента: формализм против платонизма. Вкратце, формализм говорит, что «все, что делает математик, закодировано в символах, математика — это формальный вывод теорем из аксиом посредством доказательств», в то время как платонизм говорит, что «математические объекты действительно существуют в некотором смысле, есть некое «истинное действительное» то, что вы имеете в виду, когда говорите «натуральное число», помимо того факта, что ваши доказательства натуральных чисел соответствуют символам на странице, которые следуют математическим правилам доказательства». Это философское разделение связано с нашим обсуждением выше, потому что (насколько я могу судить) формалист сказал бы, что на самом деле нет «фактов дела» о ценности$\Sigma(1000)$или любое другое значение$\Sigma$в этом отношении. Есть только тот факт, что ZFC доказывает$\Sigma(3)=6$, и ZFC не представляет никакой ценности для$\Sigma(1000)$. Хотя платоник сказал бы$\Sigma(3)$на самом деле это 6, когда я определяю «натуральное число» и компьютерные программы и так далее, я имею в виду реальную вещь, это не просто символы. Точно так же существует некоторое истинное значение$\Sigma(1000)$, если вы дадите мне какую-то конкретную компьютерную программу, если я запущу ее на своем ноутбуке, она просто остановится или не остановится, конечно, ZFC не может доказать это для всех программ, но это не значит, что это не так. правда или ложь.

Одна из причин полагать, что эта последняя позиция имеет смысл, состоит в том, что существует только одна аксиома вида$\Sigma(X)=n$, где$n$представляет собой десятичное расширение натурального числа, которое согласуется с ZFC (при условии, что ZFC совместим). Это согласуется с тем, что значение$\Sigma(1000)$не зависит от ZFC, потому что это просто гарантирует (через теорему Гёделя о полноте), что существуют две аксиомы, обе согласующиеся с ZFC:$\Sigma(1000)=n$и$\Sigma(1000) \not = n$, для некоторого явно выписанного натурального числа$n$. Удачи в выяснении того, что актуально$n$хотя!

Есть ли какая-то версия математики или системы аксиом, которая решает эту проблему? (т.е. где корректность объекта эквивалентна вычислимости?)

Существует философия математики, известная как конструктивизм , которая утверждает, что математические объекты существуют только в том случае, если их можно сконструировать явно. «Хорошо определенный» здесь не совсем правильный термин, мы должны придерживаться «существует», но в принципе это должен быть ответ, который вы ищете. Цитата из Википедии :

Если, например, принять алгоритмическую точку зрения, то построенные здесь действительные числа по сути являются тем, что классически называлось бы вычислимыми числами.

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

Я собираюсь мягко отклонить ответ res и представить альтернативную точку зрения, в которой эти сомнения, которые у вас есть, действительно оправданы.

В самом деле, вместо теории множеств, означающей ZFC с классической логикой, давайте работать в интуиционистской логике , с IZF , а не с ZFC, что довольно похоже, за исключением выбора, который нам в любом случае не нужен, когда мы говорим о машинах Тьюринга и натуральных числах.

Возьмем семейство предикатов$\Gamma(n, m)$(сказать$\Gamma(n, m):=\Sigma(n, n) = m$например) и сказать, что$\Gamma$является вычислимым числом, если существует машина Тьюринга, которая принимает на вход$n$и возвращается$m$такой, что$\Gamma(n, m)$держит.

А теперь давайте еще раз ответим на ваши 3 вопроса:

1. В IZF можно доказать существование числа 4 (и большинства чисел, которые вы можете вычислить) . Однако,$\Sigma(n, n)$в общем случае не может: вам действительно нужно доказать, что либо произвольная TM должна работать вечно, либо останавливается после определенного количества шагов. Для этого вам действительно нужна исключенная середина.

2. Существование любого «невычислимого» числа в этом смысле довольно прямо влечет за собой теорему о неполноте: если бы арифметика была полной, вы могли бы вычислить любое число, перечислив все доказательства и остановившись, как только получили, скажем, доказательство$\Gamma(\overline{n},\overline{m})$(которую вы должны в конце концов найти в законченной теории, если такая$m$существует).

3. Можно показать (предполагая некоторые стандартные и необходимые утверждения о непротиворечивости), что если$IZF \vdash \forall n\exists m, \Gamma(n,m)$тогда действительно существует вычислимая функция$f$такое, что для каждого числа$k$,$IZF\vdash \Gamma(\overline{k},\overline{f(k)})$, свойство, которое, как вы заметили, не относится к ZFC. Стоит отметить, что обратное утверждение невозможно: всегда должна быть какая-то вычислимая функция$g$такое, что нет предиката$P$с$IZF\vdash \forall n\exists m, P(n, m)$, и$P(k, l)$держится именно тогда, когда$l = g(k)$.