Существует ли биекция между вычислимыми числами и нат.?

[Nxx]

Цитата:

В этом смысле я не считаю это число чем-то принципиально отличающимся от $\pi$. Вы с этим согласны?

Согласен. Число х - вычислимое.

[PAV]

Nxx писал(а):

Согласен. Число х - вычислимое.

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

[Nxx]

Цитата:

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

Мы не знаем только до тех пор, пока все полученные знаки равны нулю. Точно также можно сказать, что мы не знаем, что больше, $\pi$ или 3,14, пока не вычислим первый знак после третьего, который не равен нулю.

[PAV]

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

[Nxx]

PAV писал(а):

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

Очевидно. Но мы будем знать, что число очень маленькое и очень близко к нулю. Если не сможем определить другим способом, останавливается алгоритм когда-то или нет.

[PAV]

Согласны ли Вы с тем, что существуют вычислимые числа, которые нельзя сравнить с нулем?

[Nxx]

PAV писал(а):

Согласны ли Вы с тем, что существуют вычислимые числа, которые нельзя сравнить с нулем?

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

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

[PAV]

PAV писал(а):

Согласны ли Вы с тем, что существуют вычислимые числа, которые нельзя сравнить с нулем?

Так "да" или "нет"?

[Nxx]

Цитата:

Так "да" или "нет"?

Если отождестлять число с задающим его алгоритмом, то да. Но такое отождествление не обязательно.

Добавлено спустя 2 минуты 56 секунд:

Про приведенный вами алгоритм мы можем сказать, что он задает вычислимое число. Задает ли он ноль или другое число, мы сказать в общем случае не можем.

[PAV]

Тогда объясните мне такой пункт Ваших взглядов. Мы выяснили, что существуют вычислимые числа, которые за конечное число операций нельзя сравнить с некоторым заданным и достаточно простым числом. Или, в более общем виде, существуют такие свойства вычислимых чисел, которые вычислить нельзя. И это вроде как не мешает им быть вычислимыми, т.е. по-Вашему "принадлежать математике". В то же самое время константе Чайнтина Вы в этом праве отказываете

Nxx писал(а):

На мой взгляд, омеги просто нет.

только лишь на том основании, что не все цифры ее десятичного разложения можно вычислить. А ведь вычисление цифры десятичного разложения математически эквивалентно сравнению исследуемого числа с определенными конечными десятичными дробями. Зато про $x$ я могу не знать, равно оно нулю или нет. А если я начну использовать какую-нибудь систему счисления, для представления в которой первым же шагом нужно сравнить число с нулем? Для константы Чайнтина я на этот вопрос ответить могу, а для $x$ - нет. Так что проясните, пожалуйста, подробнее, почему Вы в одних случаях не спорите с тем, что объекты с неполной информацией принадлежат математике, а в других исключаете их из нее на этом основании.

[Nxx]

Цитата:

Мы выяснили, что существуют вычислимые числа, которые за конечное число операций нельзя сравнить с некоторым заданным и достаточно простым числом.

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

Между нат. числами и алгоритмами есть биекция.
А вот между алгоритмами и вычислимыми числами биекции нет. Хотя для каждого вычислимого числа найдется хотя бы один алгоритм, который его задает.

[PAV]

То есть невозможность конструктивно ответить на вопрос о том, как соотносятся между собой два числа, не мешает им "принадлежать математике" и вообще существовать? Тогда почему же не существует омега? Мы же ведь некоторые ее свойства указать можем. У нее есть определение, причем все математики его однозначно понимают.

Nxx писал(а):

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

[Nxx]

Цитата:

То есть невозможность конструктивно ответить на вопрос о том, как соотносятся между собой два числа,

Не два числа, а два алгоритма. А между алгоритмами и вычислимыми числами нет взаимно-однозначного соответствия.

[epros]

маткиб писал(а):

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

Неправда Ваша. Некоторые фундаментальные теоремы конструктивно доказываются сложнее, чем классически. И это неудивительно, поскольку конструктивизм предъявляет более жёсткие требования к доказательствам. Однако на применении конструктивных теорий это практически никак не сказывается: Чтобы "конструктивно" решать дифференциальное уравнение, достаточно знать, что производная имеет конструктивное определение, все остальные действия выполняются совершенно так же, как в классической математике.

Скажу даже больше: некоторые классические заморочки в некоторых прикладных задачах исчезают. Например, исчезает различие между аддитивностью и линейностью функций, заданных на $\mathbb{R}^n$: это только классическая математика "доказывает", что могут быть нелинейные аддитивные функции (хотя примера такой функции никто никогда не видел).

маткиб писал(а):

Она страдает наличием ещё более противных здравому смыслу выводов. Одно только сравнение действительных чисел чего стоит.

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

Возьмите пример числа, которое определил PAV:

PAV писал(а):

Рассмотрим какой-нибудь алгоритм, для которого неизвестно, останавливается ли он когда-нибудь или нет. Сопоставим ему число $x$, имеющее в десятичной записи вид $0.x_1x_2x_3...$, где $x_i$ - это $0$, если на $i$-м шаге алгоритм продолжает работу или остановится на одном из предыдущих шаров, и $1$, если алгоритм остановился в точности на $i$-м шаге.

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

Конструктивная математика честно признаёт, что мы не знаем, равно ли это число нулю. Мы не можем даже сказать, будет ли когда-либо получен ответ на этот вопрос. А что же говорит классическая математика? До сих пор я не слышал ничего кроме бесполезных рассуждений на тему: "Либо это число равно нулю, либо нет, но третьего варианта быть не может".

маткиб писал(а):

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

Я удивляюсь тому, что ставятся задачи, заведомо не имеющие никакого отношения к реальности.

[маткиб]

epros писал(а):

Неправда Ваша. Некоторые фундаментальные теоремы конструктивно доказываются сложнее, чем классически. И это неудивительно, поскольку конструктивизм предъявляет более жёсткие требования к доказательствам. Однако на применении конструктивных теорий это практически никак не сказывается: Чтобы "конструктивно" решать дифференциальное уравнение, достаточно знать, что производная имеет конструктивное определение, все остальные действия выполняются совершенно так же, как в классической математике.

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

epros писал(а):

Скажу даже больше: некоторые классические заморочки в некоторых прикладных задачах исчезают. Например, исчезает различие между аддитивностью и линейностью функций, заданных на $\mathbb{R}^n$: это только классическая математика "доказывает", что могут быть нелинейные аддитивные функции (хотя примера такой функции никто никогда не видел).

В классической математике такое различие тоже исчезает, если рассматривать непрерывные функции. И почему это вообще "заморочка"?

epros писал(а):

маткиб писал(а):

Она страдает наличием ещё более противных здравому смыслу выводов. Одно только сравнение действительных чисел чего стоит.

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

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

epros писал(а):

Возьмите пример числа, которое определил PAV:

PAV писал(а):

Рассмотрим какой-нибудь алгоритм, для которого неизвестно, останавливается ли он когда-нибудь или нет. Сопоставим ему число $x$, имеющее в десятичной записи вид $0.x_1x_2x_3...$, где $x_i$ - это $0$, если на $i$-м шаге алгоритм продолжает работу или остановится на одном из предыдущих шаров, и $1$, если алгоритм остановился в точности на $i$-м шаге.

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

С точки зрения классической математики такое число существует и является действительным.

epros писал(а):

Конструктивная математика честно признаёт, что мы не знаем, равно ли это число нулю. Мы не можем даже сказать, будет ли когда-либо получен ответ на этот вопрос. А что же говорит классическая математика? До сих пор я не слышал ничего кроме бесполезных рассуждений на тему: "Либо это число равно нулю, либо нет, но третьего варианта быть не может".

Ну не отвергать же классическую математику только на основе того, что в данном конкретном случае с её помощью было получено бесполезное утверждение...

epros писал(а):

Я удивляюсь тому, что ставятся задачи, заведомо не имеющие никакого отношения к реальности.

Ну так не ставьте такие задачи