Что такое вычислимые числа и каково их философское значение?

Известно, что все математические формализации (интуитивной) вычислимости эквивалентны, в частности все они эквивалентны вычислимости на универсальной машине Тьюринга. Так что технологическая реализация не имеет значения. Тезис Черча-Тьюринга утверждает, что это совпадает по объему с тем, что «вычисляется человеком», не ограниченным ограничениями времени и ресурсов. Это явно философское утверждение, и некоторые с ним не согласны, хотя и незначительное меньшинство, но особенно ранние интуиционисты, такие как Брауэр и Вейль, Гёдель и Лукас. По их мнению, человеческий разум демонстрирует способность творчески «нарушать» алгоритмические вычисления. См. Есть ли в аргументе Гёделя о том, что разум сильнее компьютеров, лазейка для несогласованности?Более поздние интуиционисты/конструктивисты, за исключением Даммета, обычно принимают его.

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

Основное отличие состоит в том, что определимые числа могут использовать всю силу теории множеств, тогда как вычислимые числа ограничиваются ресурсами арифметики. Вот пример невычислимого, но определимого числа. Перечислить все правильные арифметические предложения числами Гёделя и определить действительное число от 0 до 1 следующим образом: n-я цифра в его десятичной записи равна 0, если n-е предложение ложно, 1, если оно истинно, и 2, если n не является числом Гёделя предложения. Он определим, потому что предикат истинности арифметики определим (в теории множеств, а не в арифметике), и мы даже можем легко вычислить некоторые из его цифр, например те, которые соответствуют доказанным теоремам или их отрицаниям. Но это невычислимо, потому что не существует алгоритма, определяющего истинность, скажем, гипотез Гольдбаха или гипотез о простых числах-близнецах. Интересно, что в то время как конструктивисты и интуиционисты отрицали существование этого числа, ранние интуиционисты признавали существование неиндивидуализированного числа.невычислимые действительные числа, основанные на прямой интуиции «становления» незаконных последовательностей, см. Подтверждено ли решение Аристотелем парадоксов Зенона движением в интуиционистском континууме?

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

http://www.daviddeutsch.org.uk/wp-content/ItFromQubit.pdf .

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

Законы физики гласят, что если вы можете выполнить определенный конечный набор вычислений и объединить эти вычисления в сети, то вы сможете выполнить любое вычисление, разрешенное законами физики. Если бы законы физики были другими, тогда можно было бы разрешить какой-то другой набор операций, и они могли бы иметь другие последствия для того, что можно вычислить. Например, см. «Начало бесконечности» Дэвида Дойча, глава 8. Таким образом, фактические законы физики допускают ограниченное подмножество множества всех возможных абстракций. В настоящее время у нас нет объяснения, почему разрешено именно это подмножество, что является философской проблемой.

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

В широком смысле философия может подойти к вопросам метавычислимости: что такое вычислимая машина или устройство? Являются ли люди вычислительными устройствами/машинами? Что такое вычислимость?

Более конкретно, философский интерес к вычислимости принимает форму математического анализа. Предоставление строгих определений и защита сложных и вычислительных устройств и функций, основанных на фундаментальных вопросах математики, таких как теория множеств.

Для более богатого чтения, чем мое, см. статью Иммермана в Стэнфордской энциклопедии философии «Вычислимость и сложность».

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

Хотя этот ответ можно считать «поверхностным», упрощенным или очевидным, по крайней мере, он предлагает другую точку зрения.
Насколько я понимаю, « вычислимое число» — это число, которое может быть вычислено «компьютером» .
Любой физический «компьютер» имеет определенные ограничения. Следовательно, любое число, лежащее «вне» ограничений компьютера, является невычислимым числом (данным компьютером).
Все физические компьютеры имеют ограничения, поэтому существуют невычислимые числа .
Одним из таких примеров является (1)/(0) (единица, деленная на ноль).

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

Моя интерпретация их «философского значения» заключается в том, что существуют «вещи», превосходящие наши возможности.