Вычислимое число это такое, которое может быть вычислено на компьютере с любой степенью точности.
Это требует уточнения. "Вычислимое число", или
конструктивное действительное число (КДЧ) — это пара алгоритмов, один из которых вычисляет последовательность рациональных чисел (то есть, по заданному натуральному числу
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
находит некоторое рациональное число
![$r_n$ $r_n$](https://dxdy-03.korotkov.co.uk/f/6/8/f/68f8ffcf43e7296c9439e6b86eccae3282.png)
), а другой называется
регулятором сходимости в себе и по заданному натуральному числу
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
вычисляет такое натуральное число
![$\beta_n$ $\beta_n$](https://dxdy-04.korotkov.co.uk/f/b/b/a/bba8a7abf043b9ff83a5da50e804e95782.png)
, что для любых
![$k>\beta_n$ $k>\beta_n$](https://dxdy-01.korotkov.co.uk/f/4/0/4/40426096be6d16a2c259b9ed4b44169582.png)
,
![$m>\beta_n$ $m>\beta_n$](https://dxdy-04.korotkov.co.uk/f/b/a/5/ba5717a291518bc49468c4b7c511f78b82.png)
выполняется неравенство
![$\lvert r_m-r_k\rvert<2^{-n}$ $\lvert r_m-r_k\rvert<2^{-n}$](https://dxdy-03.korotkov.co.uk/f/e/0/8/e085c2e8f17180dac9298730ee6e106382.png)
.
Комбинируя эти алгоритмы, мы можем вычислять число КДЧ с любой заданной точностью.
Понятие КДЧ является достаточно жёстким. Существуют различные ослабления этого понятия.
На популярном уровне алгоритм — это пошаговая инструкция, каждый шаг которой выполняется однозначно (при наличии соответствующего исполнителя, естественно). Результат применения алгоритма к исходным данным определяется в момент завершения выполнения инструкции.
Не предполагается, что этот результат должен быть в каком-нибудь смысле полезным, и даже не предполагается, что выполнение инструкции хоть когда-нибудь должно завершиться.
Существует целый ряд формализаций этого понятия: машина Тьюринга, нормальный алгорифм Маркова, частично рекурсивная функция, … Все известные формализации понятия алгоритма являются эквивалентными.
Интересно, что такое направление конструктивизма, как интуиционизм, считает ограничение понятия вычислимости алгоритмами слишком жёстким.
-- Ср фев 03, 2016 12:21:28 --Забавно, что множество алгоритмов, вычисляющих какое-то число, не перечислимо. Следовательно существуют алгоритмы, вычисляющие это число, для которых не возможно доказать, что они это делают.
Уточнение: не существует алгоритма, проверяющего, вычисляется ли заданное число заданным алгоритмом. Насчёт "невозможно доказать" ситуация более тонкая.
Конечно разрешимо, ведь мы выбросим в корзину любой текст не начинающийся со слова "доказательство".
Разумеется, надо ограничиться формальными теориями, удовлетворяющими определённым требованиям.
Во-первых, алфавит теории должен быть конечным.
Во-вторых, синтаксис теории должен быть алгоритмически распознаваемым.
В-третьих, множества аксиом и правил вывода теории должны быть алгоритмически перечислимыми (по-моему, распознаваемости всё-таки не требуется).
Такие формальные теории первого порядка, как арифметика Пеано или теория множеств ZFC этим условиям удовлетворяют.
Понятия "теорема" (обычно употребляются термины "высказывание" или "формула") и "доказательство" являются синтаксическими, поэтому можно построить алгоритм, перечисляющий тексты в заданном алфавите и проверяющий, являются ли эти тексты доказательствами заданной теоремы.
Проблема в следующем: если доказательство теоремы существует, то наш алгоритм "когда-нибудь" его найдёт. Но предположим, что мы его запустили, он проработал уже
![$10^{10^{10}}$ $10^{10^{10}}$](https://dxdy-03.korotkov.co.uk/f/a/e/1/ae1cb7322dc900338795830fb41474ed82.png)
лет и всё ещё результата не выдал. Существует доказательство или нет? Неизвестно.