Можно ли привести пример неконструктивного числа?

[Someone]

Mikhail_K в сообщении #1250015 писал(а):

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

Да, неприятности связаны с этими числами.

Mikhail_K в сообщении #1250015 писал(а):

Вроде бы, есть некое стандартное определение вычислимости, не зависящее от системы отсчёта? Где от алгоритма вычисления $q$ требуется, чтобы он на $n$-м шаге выдавал рациональное число $q_n$ такое, что $q_n\to q$ при $n\to\infty$ и чтобы $|q_{n+1}-q_n|\leq 2^{-n}$ для любого $n$. Или что-то похожее.

Примерно так. Но есть какие-то ослабления этого условия. Особенно у конструктивистов. В книге Б. А. Кушнера "Лекции по конструктивному математическому анализу" есть аж четыре варианта: FR-числа, F-числа, квазичисла, псевдочисла. Основным вариантом являются FR-числа, которые определяются по смыслу как у Вас, но всё-таки технически иначе, остальные варианты являются ослаблениями основного определения.

Mikhail_K в сообщении #1250015 писал(а):

Я ведь правильно понимаю, что если $2^{-n}$ здесь заменить на что-то другое, ничего не поменяется? Просто один шаг алгоритма с новыми требованиями будет предполагать выполнение, быть может, нескольких шагов старого алгоритма.

Разумеется.

-- Сб сен 23, 2017 15:53:53 --

Thinker в сообщении #1250019 писал(а):

Я имел в виду что-то вроде счетного множества чисел, вбирающего в себя все вышеперечисленные.

Xaositect в сообщении #1249951 писал(а):

Самого большого счетного подмножества, очевидно, нет, потому что к любому счетному подмножеству моно добавить элемент, не лежащий в нем. То же самое с подкольцами или подполями $\mathbb R$ - к любому счетному можно присоединить не лежащий в нем элемент и получить большее подкольцо/подполе.

[arseniiv]

Mikhail_K в сообщении #1250015 писал(а):

Я ведь правильно понимаю, что если $2^{-n}$ здесь заменить на что-то другое, ничего не поменяется? Просто один шаг алгоритма с новыми требованиями будет предполагать выполнение, быть может, нескольких шагов старого алгоритма.

Должно быть. Ведь идейно нам надо просто гарантировать фундаментальность последовательности, которую реализует алгоритм, а уж к вещественному числу она после этого сама собой сойдётся.

Someone в сообщении #1250030 писал(а):

В книге Б. А. Кушнера "Лекции по конструктивному математическому анализу" есть аж четыре варианта: FR-числа, F-числа, квазичисла, псевдочисла.

Ого, надо будет обязательно глянуть!

Thinker в сообщении #1250019 писал(а):

То есть в двух словах это не объяснить?

В двух словах сразу всё — нет. Но вам наверняка и не нужно сразу всё. Наверняка вам будет достаточно небольшого толчка. А вы до сих пор не сказали, что вызывает больше непонимания. Спасение рук утопающих — дело сами знаете чьё. Скажите, куда кидать круг, ибо закидывать всё море кругами нерационально, никто этого делать не станет, и придётся вам читать учебник (и это будет на самом деле не очень и страшно, но раз уж вы не хотите…).

[Ktina]

Thinker в сообщении #1249926 писал(а):

Числа бывают:
...
4. Конструируемые (те, что можно построить циркулем и линейкой).

Построить число циркулем и линейкой? Что имеется в виду? Отрезок, длина которого равна данному числу?

[arseniiv]

Длина отрезка в планиметрии — это не число, т. к. естественной единицы измерения там нет. Вот отношение длин — порядок.

[Ktina]

arseniiv
В таком случае, что же следует понимать под построением числа ЦИЛом?

[Thinker]

Ktina в сообщении #1250656 писал(а):

arseniiv
В таком случае, что же следует понимать под построением числа ЦИЛом?

Это классическая задача древности. Предположим, что нам дан единичный отрезок. Необходимо при помощи циркуля и линейки без делений за конечное число шагов построить отрезок заданной длины (которая выражается некоторым числом). Именно это и понимается под построением числа. Так можно построить любое рациональное число и некоторые алгебраические. Но не все, поэтому невозможно выполнить удвоение куба и трисекцию угла. Никакое трансцендентное число построить нельзя, поэтому неразрешима задача о квадратуре круга.
Но, все-таки, что же такое арифметическое число?

[Xaositect]

Thinker в сообщении #1250678 писал(а):

Но, все-таки, что же такое арифметическое число?

За два дня можно было бы уже что-нибудь найти и прочитать.

Но раз уж хотите, то вот Вам в двух словах: действительное число $\alpha$ является арифметическим, если для натуральных чисел $m, n$ предикат $n < |\alpha| m$ может быть выражен формулой в языке арифметики натуральных чисел. Например, $\sqrt 2$ ($n < \sqrt 2 m \Leftrightarrow n^2 < 2m^2$), $e$ ($n < em \Leftrightarrow \exists k. k^k n < (k + 1)^k m$) или константа Чайтина (сложная формула с кодированием функционирования универсальной машины, используемой в определении).

[Thinker]

Я понял! Спасибо, Вы расширили мой кругозор! Однако у меня возникла еще пара вопросов:
1. Правильно ли я понимаю, что арифметические числа образуют счетное множество?
2. А можно ли привести пример неарифметического числа?
3. Всякое ли арифметическое число является вычислимым?

[mihaild]

Thinker в сообщении #1250693 писал(а):

1. Правильно ли я понимаю, что арифметические числа образуют счетное множество?

Да, правильно. Формул же счетно.

Thinker в сообщении #1250693 писал(а):

2. А можно ли привести пример неарифметического числа?

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

[Thinker]

Спасибо! Общаться с вами приятнее, чем с моими учениками!

[arseniiv]

Thinker в сообщении #1250693 писал(а):

3. Всякое ли арифметическое число является вычислимым?

Приведённая выше константа $\Omega$ арифметична, но не вычислима.

[Thinker]

arseniiv в сообщении #1250704 писал(а):

Thinker в сообщении #1250693 писал(а):

3. Всякое ли арифметическое число является вычислимым?

Приведённая выше константа $\Omega$ арифметична, но не вычислима.

Разумеется Я перепутал. На самом деле я хотел спросить:

Всякое ли вычислимое число является арифметическим?

[george66]

Да, всякое, поскольку все перечислимые множества арифметичны. Кажется, это разбирается в популярной брошюрке Успенского "Теорема Гёделя о неполноте" (теорему о неполноте по этой брошюрке понять трудно, но попутно узнаёшь что-то интересное)

[Ktina]

Thinker в сообщении #1250678 писал(а):

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

Большое спасибо!