Большинство вещественных чисел неизвестно даже математикам
Автор: Манон Бишофф
Какое самое причудливое вещественное число вы можете себе представить? Наверное, многие подумают об иррациональном числе, таком как пи (π) или число Эйлера. И действительно, такие величины можно считать «дикими». Ведь их десятичное представление бесконечно, ни одна цифра не повторяется. Однако даже такие «дикие» числа вместе со всеми рациональными числами составляют лишь малую часть вещественных чисел, или чисел, которые можно изобразить на числовой прямой. (Напомним, что именно эти числа могут использоваться во всех привычных измерениях, включая время, температуру и расстояние).
Но оказывается, что если вы случайно выберете число на числовой прямой, то почти наверняка получите «невычислимое» число. Для таких величин не существует способа их точного определения.
Вещественные числа состоят из рациональных и иррациональных чисел. К рациональным числам (то есть числам, которые можно записать в виде дроби p⁄q, где p и q — целые числа) относятся натуральные числа (0, 1, 2, 3,…) и целые числа (…, -2, -1, 0, 1, 2,…). Остальные числа на числовой прямой — это иррациональные числа. Их тоже можно разделить на различные категории, большинство из которых мы даже не можем себе представить.
То, что бесконечности, бесконечно малые, мнимые числа и другие необычные пространства чисел трудно поддаются описанию, может показаться не слишком удивительным. Но можно было бы подумать, что мы уже полностью поняли вещественные числа, описывающие расстояния в нашем мире. К сожалению, все не так просто. Чтобы понять это, необходимо более подробно рассмотреть иррациональные числа.
Какие числа являются иррациональными?
Все действительные числа, которые не могут быть представлены в виде дроби двух целых чисел, являются иррациональными. (К иррациональным числам относится, например, квадратный корень из 2, десятичное представление которого бесконечно и никогда не повторяется. На самом деле корень из 2 относится к простейшим иррациональным числам, так как его можно построить, т.е. с помощью компаса и линейки начертить правильный треугольник с двумя сторонами, длина которых равна единице. Гипотенуза этого треугольника имеет длину √2. Аналогичным образом можно геометрически построить золотое сечение, а также многие другие иррациональные величины.
Однако уже в древности люди сталкивались с числами, которые уже не могли быть получены таким простым геометрическим способом. Известный пример — удвоение куба: как из куба с длиной стороны 1 можно построить куб вдвое большего объема? Как выяснил в 1837 году математик Пьер Ванцель, длина грани ∛2, необходимая для нового куба, не может быть построена с помощью компаса и линейки. Но ∛2 относится к алгебраическим числам, которые можно записать как решение полиномиального уравнения. Для ∛2 соответствующее уравнение имеет вид x3 = 2.
Некоторые числа являются трансцендентными
Существуют также трансцендентные числа, которые не могут быть выражены в виде решения подобных уравнений. То есть не существует простой формулы, с помощью которой их можно было бы вычислить. Известно, что π относится к этой категории. Но это не значит, что мы не знаем его значения. Греческий математик Архимед нашел правило вычисления, позволяющее определить π, по крайней мере, приблизительно. Кроме того, существует множество алгоритмов, позволяющих произвольно вычислить 587-миллионный десятичный знак числа π. При достаточной вычислительной мощности и времени это число может быть определено с произвольной точностью, по крайней мере, теоретически. То же самое относится и к числу Эйлера (e), или 2√2.
Трансцендентные числа таят в себе несколько загадок. В то время как существуют четкие методы, позволяющие определить, является ли число конструируемым, доказать трансцендентность той или иной величины, напротив, достаточно сложно. Например, в 1934 году советский математик Александр Гельфонд смог доказать, что составное число eπ трансцендентно. Но являются ли величины πe, π x e или π — e алгебраическими или трансцендентными, до сих пор неясно.
Невычислимые числа ещё более странные
До начала XX века люди считали, что трансцендентные числа — это самое дикое, что есть в вещественных числах. Но это оказалось неверно. В 1937 году британский математик Алан Тьюринг опубликовал работу о вычислимых числах. Он использовал этот термин для обозначения всех тех величин, для которых существует правило вычисления (то есть алгоритм), выполнив которое компьютер может вычислить числовое значение с любой степенью точности.
Практически все известные трансцендентные числа, такие как π и e, попадают в эту категорию. Ведь мы знаем их хотя бы приблизительное числовое значение, а также то, как их можно вычислить. Однако, как показал в своей работе Тьюринг, существуют столь же невычислимые числа, значения которых не могут быть приближены с произвольной точностью, т.е. мы не имеем ни малейшего представления о том, как они выглядят.
Хуже того: почти все вещественные числа не вычислимы.
Это становится понятно, если задуматься о бесконечных размерах различных наборов чисел. Математик Георг Кантор заложил основы этой идеи в конце XIX века. Тогда ему удалось показать, например, что множества натуральных, целых и рациональных чисел имеют одинаковую кардинальность (математическое выражение, обозначающее размер множества). Каким образом? Для того чтобы понять это, необходимо прежде всего отметить, что те же правила вычислений для конечных чисел не применимы к бесконечным. Возьмем, к примеру, натуральные и целые числа: каждому натуральному числу можно поочередно присвоить положительное и отрицательное целое число, скажем, (0, 0), (1, -1), (2, 1), (3, -2), (4, 2) и т.д. Поскольку натуральных чисел не существует, то мы нашли отображение один к одному между этими двумя множествами. Это похоже на то, как если бы каждому человеку на остановке было выделено ровно одно место в автобусе, и наоборот. В этом случае мы знаем, что мест в автобусе столько же, сколько людей на остановке. Аналогично обстоит дело с натуральными и целыми числами.
Аналогичное отображение один к одному можно найти между рациональными и натуральными числами. Как удалось показать Кантору, кардинальность натуральных чисел — это наименьшая возможная бесконечность. Он назвал ее «счетно бесконечной».
Вещественные числа, с другой стороны, не поддаются счету. Кантору удалось доказать, что кардинальность действительных чисел обязательно больше кардинальности натуральных. Для этого он показал, что невозможно перечислить все действительные числа в списке (каким бы длинным он ни был), не пропустив некоторые значения. Таким образом, вещественные числа образуют несчетное множество.
Кантор рассуждал следующим образом: предположим, что имеется список всех действительных чисел. Тогда этот список можно представить в виде таблицы. В каждой строке находится число, а в каждом столбце — место для десятичного знака. Кантор показал, что если очертить круг вокруг набора чисел, образующих диагональ таблицы (например, первая цифра в первой строке, вторая цифра во второй строке и т. д.), то можно создать новое действительное число, прибавив к каждой записи диагонали 1. Это новое число не может содержаться в списке. Таким образом, ваш первоначальный список всех действительных чисел является неполным.
Но, как утверждал Тьюринг, все вычислимые числа должны быть счетными. Для каждого из этих чисел можно разработать машину, которая просто вычисляет его значение. Поскольку эти вычислительные машины можно пронумеровать, вычислимые числа обязательно должны быть счетными. Это, в свою очередь, приводит к тому, что невычислимые числа составляют подавляющее большинство реальных чисел: их несчетное количество!
Поэтому, если посчитать вероятность того, какое вещественное число попадется при случайной выборке, то получится однозначный результат: в 100% случаев это число не будет вычислимым. Но это не значит, что нельзя вытянуть любое другое число. При бесконечном множестве событий вероятность нуля не означает, что исход невозможен.
Невычислимых чисел очень много, и тем более удивительно, что их известно не так уж много
Немногочисленные существующие примеры невычислимых чисел были определены знаменитой проблемой остановки (halting problem) из информатики. Чтобы понять суть этой проблемы, разработанной Тьюрингом, представьте себе компьютер, выполняющий определенный набор инструкций для решения какой-либо задачи (другими словами, компьютер использует алгоритм). В проблеме остановки предлагается представить себе машину, которая могла бы определить, остановится ли компьютер, выполняющий заданный алгоритм, в какой-то момент или будет продолжать работу вечно. Как доказал Тьюринг, хотя такая машина может определить, могут ли некоторые алгоритмы выполняться за конечное время, очевидно, что не существует метода, который мог бы сделать это для всех возможных программных кодов. Проблема остановки является прямым применением теоремы о неполноте математика Курта Геделя, которая утверждает, что не все математические утверждения могут быть доказаны.
Проблема остановки была использована аргентинско-американским математиком Грегори Хайтином для определения невычислимого числа. Так называемая константа Хайтина Ω соответствует вероятности, с которой теоретическая модель компьютера (машина Тьюринга) останавливается для любого заданного входа: Ω = -∑p½|p|, где p обозначает все программы, которые завершаются после конечного времени выполнения, а |p| описывает длину программы в единицах бит.
Таким образом, для точного вычисления константы Хайтина необходимо знать, какие программы завершаются, а какие нет, что, согласно проблеме остановки, невозможно. Тем не менее, в 2000 году математику Кристиану С. Калуде и его коллегам удалось вычислить первые цифры константы Хайтина: 0,0157499939956247687…..
Это означает, что если случайно сгенерировать программу на языке, который использовали Калуде и его коллеги, то она завершится с вероятностью около 1,58% за конечное время выполнения. Даже если результат имеет высокую точность, константа Хайтина не может быть вычислена с произвольной точностью.
Невычислимое число и занятой бобер
Еще одно невычислимое число получается из «функции занятого бобра», или BB(n). Эта функция вычисляет наибольший возможный выход (измеряемый в битах), который алгоритм может получить из n битов.
Например, невычислимое число получается из следующей конструкции: ∑n½BB(n). Пока известны только первые четыре значения функции «занятый бобер». Два других значения можно, по крайней мере, оценить.
Таким образом, первые цифры этого неисчислимого числа равны ∑n½BB(n) = 0,51562548…..
Существуют и другие сложные методы определения невычислимых чисел. Возможно, вы тоже сможете придумать свой вариант. Тем не менее, учитывая обилие известных нам вычислимых чисел, всегда удивительно, что невычислимые величины доминируют среди вещественных чисел, а значит, и в нашем мире.
Оригинал: Scientific American
