Вычислимое число
В математике вычислимые числа — это действительные числа , которые могут быть вычислены с любой желаемой точностью с помощью конечного завершающего алгоритма . Они также известны как рекурсивные числа , эффективные числа [1] или вычислимые действительные числа или рекурсивные действительные числа . [ нужна ссылка ]
Эквивалентные определения могут быть даны с использованием µ-рекурсивных функций , машин Тьюринга или λ-исчисления в качестве формального представления алгоритмов. Вычислимые числа образуют реальное замкнутое поле и могут использоваться вместо действительных чисел во многих, но не во всех, математических целях.
Далее Марвин Мински определяет числа, подлежащие вычислению, аналогично тому, как это определил Алан Тьюринг в 1936 году; [2] т. е. как «последовательности цифр, интерпретируемые как десятичные дроби» от 0 до 1: [3]
Вычислимое число [это] число, для которого существует машина Тьюринга, которая при заданном n на ее исходной ленте заканчивается n -й цифрой этого числа [закодированного на ее ленте].
Ключевыми понятиями в определении являются (1) то, что некоторое n задано в начале, (2) для любого n вычисление занимает только конечное число шагов, после чего машина выдает желаемый результат и завершает работу.
Альтернативная форма (2) — машина последовательно печатает все n цифр на своей ленте, останавливаясь после печати n -й — подчеркивает наблюдение Мински: (3) что при использовании машины Тьюринга конечное определение — в форме таблицы состояний машины — используется для определения потенциально бесконечной строки десятичных цифр.
