Константа Чайтина является примером (фактически семейством примеров) невычислимого числа. Это представляет вероятность того, что случайно сгенерированная программа (в определенной модели) остановится. Его можно вычислить приблизительно, но (доказуемо) не существует алгоритма его вычисления с произвольной точностью.
Что делает число вычислимым?
Вычислимое число - это число, которое может быть вычислено конечной компьютерной программой. Все числа, о которых вы когда-либо слышали, такие как 3, √2, π, e и т. д., вычислимы. Некоторые числа (например, π) представлены бесконечной последовательностью неповторяющихся цифр.
Что значит невычислимое?
Невычислимой является задача, для которой не существует алгоритма, который можно использовать для ее решения. Самым известным примером невычислимости (или неразрешимости) является проблема остановки.
Существуют ли невычислимые числа?
Мало того, что невычислимые числа существуют, но на самом деле их намного больше, чем вычислимых чисел. Многие, многие действительные числа представляют собой просто бесконечные последовательности, казалось бы, случайных цифр, без закономерностей или особых свойств. … В качестве одного из таких примеров рассмотрим число, часть которого до запятой равна 0.
Вычислимы ли действительные числа?
Вещественное число вычислимо тогда и только тогда, когда множество натуральных чисел, которое оно представляет (если оно записано в двоичном виде и рассматривается как характеристическая функция), вычислимо. Каждый вычислимыйчисло арифметическое.
