2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Можно ли привести пример неконструктивного числа?
Сообщение22.09.2017, 19:39 


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

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение22.09.2017, 19:57 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Thinker в сообщении #1249833 писал(а):
1. Конструктивное число и вычислимое число - это одно и то же или нет? Если нет, то в чем разница?
Да. Термин "конструктивное (действительное) число" реже встречается, но означает то же самое, что "вычислимое (действительное) число".

Thinker в сообщении #1249833 писал(а):
2. Можно ли привести пример неконструктивного числа?
Омега Чайтина

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 00:34 


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

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 00:37 
Заслуженный участник


27/04/09
28128
Так там же ссылка стоит.

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

Вот сюда.

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 00:45 


10/09/13
39
Санкт-Петербург
Да, стоит, но от нее так мало толку! Непонятное определяют через непонятное. Объясните, пожалуйста, по-русски)

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 01:02 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 01:17 
Заслуженный участник


27/04/09
28128
Thinker в сообщении #1249899 писал(а):
Непонятное определяют через непонятное. Объясните, пожалуйста, по-русски)
Так вы скажите, что именно вам не ясно (если многое, начните с чего-нибудь). А то на каком уровне объяснять, непонятно.

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 03:36 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 06:38 


10/09/13
39
Санкт-Петербург
arseniiv в сообщении #1249911 писал(а):
Thinker в сообщении #1249899 писал(а):
Непонятное определяют через непонятное. Объясните, пожалуйста, по-русски)
Так вы скажите, что именно вам не ясно (если многое, начните с чего-нибудь). А то на каком уровне объяснять, непонятно.

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

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 11:39 
Заслуженный участник
Аватара пользователя


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

Thinker в сообщении #1249926 писал(а):
Я полагал, что "самое большое" счетное подмножество вещественных чисел - это вычислимые числа, к каковым относятся все алгебраические, е, пи, числа Лиувилля и т. п.
Самого большого счетного подмножества, очевидно, нет, потому что к любому счетному подмножеству моно добавить элемент, не лежащий в нем. То же самое с подкольцами или подполями $\mathbb R$ - к любому счетному можно присоединить не лежащий в нем элемент и получить большее подкольцо/подполе.

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 11:53 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 13:14 
Заслуженный участник
Аватара пользователя


16/07/14
9211
Цюрих
atlakatl в сообщении #1249955 писал(а):
Вощет, алгебраические числа образуют поле, потому многочлены сами могут иметь алгебраические коэффициенты.
Есть теорема, что это одно и то же (корень многочлена с алгебраическими коэффициентами является и корнем многочлена с рациональными).

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 14:30 
Заслуженный участник
Аватара пользователя


23/07/05
17991
Москва
Thinker в сообщении #1249926 писал(а):
6. Вычислимые (те, для вычисления которых существует алгоритм).
Вот в этом месте сидит большая пакость. Во-первых, существует больше одного определения вычислимости (конструктивности) действительного числа, причём, они не все равносильны. Во-вторых, если под вычислимостью понимать существование алгоритма, выписывающего последовательность цифр числа в некоторой системе счисления, то оказывается, что число, вычислимое в одной системе счисления, может не быть таковым в другой системе счисления.

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 14:48 
Заслуженный участник
Аватара пользователя


26/01/14
4855
Someone в сообщении #1250010 писал(а):
Вот в этом месте сидит большая пакость. Во-первых, существует больше одного определения вычислимости (конструктивности) действительного числа, причём, они не все равносильны. Во-вторых, если под вычислимостью понимать существование алгоритма, выписывающего последовательность цифр числа в некоторой системе счисления, то оказывается, что число, вычислимое в одной системе счисления, может не быть таковым в другой системе счисления.
Наверное, этот эффект связан с неоднозначностью представления некоторых чисел в системах счисления (типа, с бесконечной последовательностью нулей и девяток на конце в случае десятичной системы)?

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

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

 Профиль  
                  
 
 Re: Можно ли привести пример неконструктивного числа?
Сообщение23.09.2017, 14:57 


10/09/13
39
Санкт-Петербург
Xaositect в сообщении #1249951 писал(а):
Ну вы же прочитали учебники матана, алгебры, теории алгоритмов и конструктивного анализа, чтобы разобраться с Вашим списком, почему Вы думаете, что дальше будет быстрее?

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

-- 23.09.2017, 16:04 --

Xaositect в сообщении #1249951 писал(а):
Thinker в сообщении #1249926 писал(а):
Я полагал, что "самое большое" счетное подмножество вещественных чисел - это вычислимые числа, к каковым относятся все алгебраические, е, пи, числа Лиувилля и т. п.
Самого большого счетного подмножества, очевидно, нет, потому что к любому счетному подмножеству моно добавить элемент, не лежащий в нем.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: mihaild


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group