Конструктивность действительных чисел

[epros]

Здесь Руст поднял вопрос о конструктивности действительных чисел. Я всё же полагаю понятие действительного числа само по себе конструктивным, но не без некоторых проблем.

Давайте для начала остановимся на каком-нибудь удобном определении. Пусть "действительное число" у нас определяется через его двоичную запись, а именно:
1. Имеем тройку ("знак","порядок","мантисса"), где "порядок" - любое целое число, означающее соответствующую степень двойки, а "мантисса" - запись числа в диапазоне [0,1).
2. Мантисса представляет собой бесконечную последовательность 0 и 1 (разрядов), такую, что какой бы номер разряда k мы ни взяли, последовательность разрядов после k не состоит из одних единиц (одни нули допустимы).
3. Все числа с нулевой мантиссой равны (т.е. порядок и знак для них не имеет значения).

В принципе, такое понятие действительного числа вполне конструктивно в том смысле, что если определён конечный алгоритм для определения любого разряда, то число определено. Например, число $\pi$ определено.

Вопросы у меня возникают по-поводу того, определены ли операции над действительными числами. Например, двуместная операция сложения. В двоичной записи она сводится к поразрядному сложению с учётом переносов из младших разрядов. Вот в этом переносе и состоит вопрос. А можем ли мы вообще с помощью гарантированно конечного алгоритма вычислить любой k-тый разряд суммы? Ведь для этого потребуется проверка наличия переносов из младшего разряда, которая потребует наличия проверки переноса из ещё более младшего разряда и т.д. Цепочка проверок оборвётся только тогда, когда в одном и том же разряде обоих слагаемых окажутся оба нули. Но ведь нет никаких гарантий того, что это когда-то случится...

[Руст]

Конструктивными называются числа, у которых все цифры могут быть получены конечным алгоритмом от конечного числа данных. Поэтому количество конструктивных чисел счётно.

[epros]

Руст писал(а):

Конструктивными называются числа, у которых все цифры могут быть получены конечным алгоритмом от конечного числа данных. Поэтому количество конструктивных чисел счётно.

Мне такое определение представляется излишне жёстким. Что неконструктивного в числе $\pi$? Да, все его цифры нельзя получить конечным алгоритмом. Ну и что? Зато любое конечное множество любых цифр можно получить конечным алгоритмом. Кому нужно большее?

[Руст]

epros писал(а):

Руст писал(а):

Конструктивными называются числа, у которых все цифры могут быть получены конечным алгоритмом от конечного числа данных. Поэтому количество конструктивных чисел счётно.

Мне такое определение представляется излишне жёстким. Что неконструктивного в числе $\pi$? Да, все его цифры нельзя получить конечным алгоритмом. Ну и что? Зато любое конечное множество любых цифр можно получить конечным алгоритмом. Кому нужно большее?

Последнее экввалентно конструктивности, если под алгоритмом понимаем одно и то же (не какой нибудь, ссылающийся на случайные события, правда и числа при этом случайные). Так, что любое число, что вы можете предъявить явно, является конструктивным.

[epros]

Руст писал(а):

Последнее экввалентно конструктивности, если под алгоритмом понимаем одно и то же (не какой нибудь, ссылающийся на случайные события, правда и числа при этом случайные). Так, что любое число, что вы можете предъявить явно, является конструктивным.

Значит вначале я Вас не так понял. Действительно, сразу все цифры получить конечным алгоритмом невозможно - даже если получение и запись конечного множества цифр составляет одну операцию, то только на запись всех цифр потребуется бесконечное количество операций, т.е. алгоритм записи получится бесконечным (т.е. никогда не сможет быть выполнен).

Так что в моём понимании "явно предъявить число" означает "однозначно определить конечный алгоритм получения любой его цифры".

Но как же быть с суммой? Можно ли доказать, например, что 100-миллионную цифру для $\pi + \sqrt2$ можно получить посредством выполнения конечного количества операций над цифрами?

И если это в общем случае для любых действительных чисел недоказуемо, то не значит ли это, что конструктивная операция сложения для действительных чисел не может быть определена?

[Руст]

Для конструктивных чисел можно определить все цифры конструктивно, другое дело мы заранее не можем сказать является ли число вида $\frac{a}{10^k}$, т.е. когда начинают появляться цифры-девятки после некоторого номера, мы заранее не знаем, закончатся они или нет.

[Егор]

Эта тема расписана, к примеру, в учебнике Кушнера. Попробую написать краткий конспект.

Термины "целое число", "рациональное число", "последовательность" будем всюду понимать конструктивно: целые и рациональные числа задаются как двоичные или десятичные записи, последовательности - как алгоритмы (машины Тьюринга).

Если $r$ - целое число, $r>1$, то назовём $r$-ичными дробями выражения вида

\[m+\sum_{n=1}^\infty\frac{a(n)}{r^n}\]

,
где $m$ - целое число, $a$ - последовательность целых чисел, причём $0\le a(n)<r$ для любого натурального $n$.

Конечно, $r$-ичные дроби являются примерами конструктивных действительных чисел (КДЧ), но совершенно не годятся на роль всех КДЧ.

Во-первых, при любом целом основании $r$, $r>1$, не существует алгоритма сложения конструктивных $r$-ичных дробей.

Во-вторых, алгоритм перевода из $r$-чных в $s$-чные дроби существует только тогда, когда каждый простой делитель $s$ является простым делителем $r$ (теорема Мостовского-Успенского). Например, существует алгоритм для перевода десятичных дробей в двоичные, но не существует алгоритма для перевода двоичных дробей в десятичные.

Естественно определять КДЧ как фундаментальные последовательности рациональных чисел с конструктивными регуляторами фундаментальности.

Более формально. Конструктивным действительным числом назовём пару $(A,B)$, где $A$ и $B$ - алгоритмы, определённые для любого натурального входа, причём $A(n)$ рационально для любого натурального $n$, $B(n)$ натурально для любого натурального $n$ и

\[ |A(n)-A(m)|<2^{-k}\quad\text{при}\quad n,m\ge B(k). \]

Имеется много определений КДЧ, равносильных этому. Для КДЧ нетрудно определить арифметические операции и отношения больше-меньше-равно. При этом существуют алгоритмы для операций сложения и умножения, но не существует алгоритма для сравнения. Кроме того, разные пары алгоритмов $(A_1,B_1)$, $(A_2,B_2)$ могут порождать равные КДЧ.

Для любого натурального $r$, $r>1$, существует алгоритм перевода $r$-ичной дроби в КДЧ, но не существует обратного алгоритма.

[Егор]

epros писал(а):

Но как же быть с суммой? Можно ли доказать, например, что 100-миллионную цифру для $\pi + \sqrt2$ можно получить посредством выполнения конечного количества операций над цифрами?

В данном примере можно. Число $\pi+\sqrt2$ трансцендентное, поэтому иррациональное, поэтому его разложение не может заканчиваться на все девятки и не может заканчиваться на все нули, поэтому любую его цифру можно вычислить.

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

\[x=1-\sum_{k=1}^\infty\frac{a_k}{10^k},\]

где $a_k=1$, если $2k+1$ является совершенным числом, и $a_k=0$ в противном случае. Число $x$ можно вычислить с любой точностью, так что это КДЧ. Но неизвестно, существуют ли нечётные совершенные числа. Поэтому неизвестно, $x=1$ или $x<1$.

[yvanko]

По идее, удобнее говорить не "вычислить любую цифру" а "вычислить с любой точностью"

[Егор]

yvanko писал(а):

По идее, удобнее говорить не "вычислить любую цифру" а "вычислить с любой точностью"

Это просто разные вещи (из первого следует второе, но не наоборот). Не "удобнее говорить", а правильнее так определять КДЧ.

[Someone]

Егор писал(а):

yvanko писал(а):

По идее, удобнее говорить не "вычислить любую цифру" а "вычислить с любой точностью"

Это просто разные вещи (из первого следует второе, но не наоборот). Не "удобнее говорить", а правильнее так определять КДЧ.

Да. Потому что "конструктивность" в смысле возможности вычислить любую цифру зависит от выбранной системы счисления.

[epros]

Егор писал(а):

epros писал(а):

Но как же быть с суммой? Можно ли доказать, например, что 100-миллионную цифру для $\pi + \sqrt2$ можно получить посредством выполнения конечного количества операций над цифрами?

В данном примере можно. Число $\pi+\sqrt2$ трансцендентное, поэтому иррациональное, поэтому его разложение не может заканчиваться на все девятки и не может заканчиваться на все нули, поэтому любую его цифру можно вычислить.

Непонятно. Переносы возникают не только когда в разложении слагаемого идут сплошные девятки. Например 7 в одном слагаемом и 5 в другом дадут перенос. Вариантов много.

Поэтому, чтобы не мучиться со множеством вариантов я предложил двоичную запись действительного числа. Там перенос:
1. точно не возникает только если у обоих слагаемых в данном разряде нули.
2. может возникнуть (т.е. требуется проверка переноса из следующего разряда), если в данном разряде у слагаемых разные цифры
3. точно возникнет, если у обоих слагаемых в данном разряде единицы

Доказуемо ли, что для $\pi$ и для $\sqrt2$ после100-миллионного разряда ситуация (1) возникнет хотя бы для одного разряда? (Т.е. что алгоритм сложения непременно закончится.)
Доказуемо ли это в общем случае (для любой пары действительных чисел)?

yvanko писал(а):

По идее, удобнее говорить не "вычислить любую цифру" а "вычислить с любой точностью"

Я не понял, что значит вычислить цифру "с точностью"? Цифра - это элемент конечного множества цифр. Вычислить её - это значит "указать конкретный элемент" этого множества.

[RIP]

epros писал(а):

yvanko писал(а):
По идее, удобнее говорить не "вычислить любую цифру" а "вычислить с любой точностью"

Я не понял, что значит вычислить цифру "с точностью"? Цифра - это элемент конечного множества цифр. Вычислить её - это значит "указать конкретный элемент" этого множества.

Имелось в виду "вычислить число с любой точностью"(вместо "вычислить его любую цифру")

[epros]

RIP писал(а):

Имелось в виду "вычислить число с любой точностью"(вместо "вычислить его любую цифру")

Ну ладно, если охота ещё определять что такое "точность" числа, то пожалуйста. Но вообще-то как я понимаю, это то же самое, что вычислить любую цифру.

[Егор]

epros писал(а):

Ну ладно, если охота ещё определять что такое "точность" числа, то пожалуйста. Но вообще-то как я понимаю, это то же самое, что вычислить любую цифру.

В том-то и дело, что не то же самое! Вычислить действительное число $x$ с точностью $\varepsilon$ -- значит найти такое рациональное $q$, что $|x-q|<\varepsilon$. Можем уметь вычислять $x$ с любой точностью, но не знать даже первую его цифру (см. выше пример, связанный с задачей о нечётных совершенных числах).

epros писал(а):

Непонятно. Переносы возникают не только когда в разложении слагаемого идут сплошные девятки. Например 7 в одном слагаемом и 5 в другом дадут перенос. Вариантов много.

Там шла речь о сплошных девятках или нулях не в слагаемых, а в сумме.

Вот подробное рассуждение для суммы чисел в двоичной записи. Пусть $a$ и $b$ заданы как двоичные дроби, и пусть известно, что их сумма $x=a+b$ иррациональна. Покажем, что можно вычислить целую часть $x$ (аналогично и любую цифру). Раскладывая $a$ и $b$ до первой цифры после запятой, получим, например: $a=0.1\ldots$, $b=0.0\ldots$, т. е.

$$ 0.1\le a\le 1.0,\quad 0.0\le b\le 0.1. $$

Отсюда

$$ 0.1\le x\le 1.1. $$

На первом шаге мы не смогли узнать целую часть $x$. Такая "плохая" ситуация может сохраниться и на втором шаге:

$$ 0.11\le x\le 1.01. $$

Предположим, что "плохая" ситуация будет всегда: левое приближение $<1$, правое приближение $>1$. Но тогда $x=1$, что противоречит условию. Значит, либо на некотором шаге либо левое приближение станет $\ge 1$, и тогда $\lfloor x\rfloor=1$, либо правое приближение станет $\le1$, и тогда $\lfloor x\rfloor=0$ (случай $x=1$ исключаем, так как $x$ иррационально).

"Плохая" ситуация соответствует случаю 2 по Вашей классификации (у одного слагаемого цифра 1, у другого - 0), "хорошие ситуации" - случаям 3 и 1.