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

[Thinker]

Здравствуйте!
В моем уме родились два вопроса:
1. Конструктивное число и вычислимое число - это одно и то же или нет? Если нет, то в чем разница?
2. Можно ли привести пример неконструктивного числа?

[Xaositect]

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

1. Конструктивное число и вычислимое число - это одно и то же или нет? Если нет, то в чем разница?

Да. Термин "конструктивное (действительное) число" реже встречается, но означает то же самое, что "вычислимое (действительное) число".

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

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

Омега Чайтина

[Thinker]

Большое спасибо!
А еще я прочитал в Википедии, что любое вычислимое число является арифметическим. Объясните, пожалуйста, что такое арифметическое число и чем это понятие отличается от понятия вычислимого числа.

[arseniiv]

Так там же ссылка стоит.

-- Сб сен 23, 2017 02:38:55 --

Вот сюда.

[Thinker]

Да, стоит, но от нее так мало толку! Непонятное определяют через непонятное. Объясните, пожалуйста, по-русски)

[mihaild]

См., например, Верещагин, Шень, "Вычислимые функции" (наверное не лучший источник про арифметические множества, но сойдет).

[arseniiv]

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

Непонятное определяют через непонятное. Объясните, пожалуйста, по-русски)

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

[george66]

Есть "язык арифметики первого порядка", он содержит (в одном из равносильных вариантов)
$n,m,k\ldots$ переменные для натуральных чисел
$0,1$ константы для нуля и единицы
$+, \times$ символы для сложения и умножения
$=$ знак равенства
$\neg,\wedge,\vee,\Rightarrow$ логические связки
$\forall,\exists$ кванторы
$()$ скобки
Множества натуральных чисел, которые можно задать формулами этого языка, называются арифметическими. Например, множество чётных чисел задаётся следующей формулой $\varphi(n)$
$\exists m (n=m+m)$
С помощью некоторого хитрого кодирования в этом языке можно говорить о конечных списках натуральных чисел произвольной длины. Это позволяет определить огромное количество всяких множеств (например, множество простых чисел является арифметическим). Тем не менее, есть и не арифметические множества, хотя бы из соображений мощности (арифметических множеств только счётное число).

[Thinker]

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

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

Непонятное определяют через непонятное. Объясните, пожалуйста, по-русски)

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

Ок. Тогда начну с того, в чем мне удалось разобраться.
Числа бывают:
1. Натуральные (целые положительные).
2. Целые (положительные, отрицательные и ноль).
3. Рациональные (отношение целого и натурального).
4. Конструируемые (те, что можно построить циркулем и линейкой).
5. Алгебраические (корни многочленов с рациональными коэффициентами).
6. Вычислимые (те, для вычисления которых существует алгоритм).
7. Вещественные (точки числовой прямой).
В этом списке каждое последующее множество является надмножеством предыдущего. №№ 1 - 6 образуют счетные множества, № 7 - несчетное (континуум). Вещественные числа можно разделять на целые и дробные, рациональные и иррациональные, алгебраические и трансцендентные, вычислимые и невычислимые.
А теперь то, что мне не понятно.
Я полагал, что "самое большое" счетное подмножество вещественных чисел - это вычислимые числа, к каковым относятся все алгебраические, е, пи, числа Лиувилля и т. п. Но, оказывается, существуют еще какие-то загадочные арифметические числа, которые, как логично предположить, могут быть или не быть вычислимыми...
Неужели, чтобы получить хотя бы примерное представление о том, что это такое, необходимо прочитать сотни страниц математического текста?

[Xaositect]

Ну вы же прочитали учебники матана, алгебры, теории алгоритмов и конструктивного анализа, чтобы разобраться с Вашим списком, почему Вы думаете, что дальше будет быстрее?

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

Я полагал, что "самое большое" счетное подмножество вещественных чисел - это вычислимые числа, к каковым относятся все алгебраические, е, пи, числа Лиувилля и т. п.

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

[atlakatl]

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

5. Алгебраические (корни многочленов с рациональными коэффициентами).
6. Вычислимые (те, для вычисления которых существует алгоритм).

Вощет, алгебраические числа образуют поле, потому многочлены сами могут иметь алгебраические коэффициенты.

[mihaild]

atlakatl в сообщении #1249955 писал(а):

Вощет, алгебраические числа образуют поле, потому многочлены сами могут иметь алгебраические коэффициенты.

Есть теорема, что это одно и то же (корень многочлена с алгебраическими коэффициентами является и корнем многочлена с рациональными).

[Someone]

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

6. Вычислимые (те, для вычисления которых существует алгоритм).

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

[Mikhail_K]

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

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

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

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

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

[Thinker]

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

Ну вы же прочитали учебники матана, алгебры, теории алгоритмов и конструктивного анализа, чтобы разобраться с Вашим списком, почему Вы думаете, что дальше будет быстрее?

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

-- 23.09.2017, 16:04 --

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

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

Я полагал, что "самое большое" счетное подмножество вещественных чисел - это вычислимые числа, к каковым относятся все алгебраические, е, пи, числа Лиувилля и т. п.

Самого большого счетного подмножества, очевидно, нет, потому что к любому счетному подмножеству моно добавить элемент, не лежащий в нем.

Да это понятно, я ведь не случайно взял слова "самое большое" в кавычки. Все счетные множества "одинаково большие" и равномощны множеству натуральных чисел. Я имел в виду что-то вроде счетного множества чисел, вбирающего в себя все вышеперечисленные. Конечно, это очень нестрого, но, думаю, Вы понимаете, о чем речь.