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

[Nxx]

Цитата:

Лучше скажите: какие есть основания считать, что весь (ну буквально весь) мир выразим в конечных терминах?

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

[ewert]

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

[Nxx]

ewert писал(а):

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

Не утверждал такого. Утверждал только, что

(1) Приборы в результате измерений получают только рациональные числа.

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

(3) Существование компьютеров, которые решают проблему останова противоречит известным на сегодня законам физики.

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

Соответственно, невычислимые величины

(1) Не наблюдаемы в природе
(2) Не вычислимы в имеющихся и теоретически возможных компьютерах

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

[ewert]

Тогда уж будьте последовательны. Числа "пи" тоже в природе не существует -- ибо никто и никогда не сосчитал (ну да, пока, всего лишь пока) все его знаки.

[Nxx]

>Тогда уж будьте последовательны. Числа "пи" тоже в природе не существует -- ибо никто и никогда не сосчитал (ну да, пока, всего лишь пока) все его знаки.

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

[ewert]

да, но ить никакие приборы сего числа не регистрируют.. А вот это уже трагедь. Однозначно.

[маткиб]

epros в сообщении #184692 писал(а):

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

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

[epros]

ewert писал(а):

А вот это уже трагедь. Однозначно.

Для кого это трагедия? Я, например, совершенно спокойно отношусь к тому, что какие-то из цифр числа пи пока неизвестны.

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

Но математические утверждения - они всегда об устройстве какого-то вымышленного мира.

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

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

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

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

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

[Nxx]

Цитата:

однако по эффективности применений

Скажи пожалуйста, какие конкретно задачи из реальной жизни требуют актуальную бесконечность, аксиому выбора, использование невычислимыхз чисел и т.д.?

Если эти задачи нельзя решить без этих теоретико-множественных средств, значит и правда, невычислимые величины, актуальные бесконечности и т.д. существуют в природе. Так что, приведи пример.

Если таких задач нет, то нечего говорить про "эффективность" теории, которая не помогает решить ни одну жизненную задачу.

[маткиб]

epros писал(а):

В прикладных науках она применима совершенно везде, где вообще находит применение математика.

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

epros писал(а):

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

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

epros писал(а):

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

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

[ewert]

Nxx в сообщении #185034 писал(а):

Скажи пожалуйста, какие конкретно задачи из реальной жизни требуют актуальную бесконечность, аксиому выбора, использование невычислимыхз чисел и т.д.?

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

Однако обращаю внимание: в конструктивном смысле этой задачи просто не существует. Поскольку не существует "непрерывных функций вообще".

И вот теперь надо как-то решать какое-нибудь уравнение. Застрелиться, что ли?...

[маткиб]

Nxx писал(а):

Цитата:

однако по эффективности применений

Скажи пожалуйста, какие конкретно задачи из реальной жизни требуют актуальную бесконечность, аксиому выбора, использование невычислимыхз чисел и т.д.?

Примеров, которые принципиально неподвластны конструктивной математике, я не знаю, хотя и не исключаю, что они существуют. Например, в теории сложности (в том числе в её прикладной части) много открытых проблем, которые не обязаны решаться конструктивными методами. Например, никто и никогда не доказал такого утверждения, что если в ZFC можно доказать, что алгоритм A решает задачу "выполнимость" за полиномиальное время, то то же самое можно сделать и в конструктивной теории (не знаю, какая там у вас наиболее общепринятая аксиоматика). Аксиома выбора здесь, конечно, не нужна, но вот актуальная бесконечность (в том числе несчётная), не исключено, что и потребуется.

Но есть куча примеров из реальной жизни, когда классическая математика оказывается намного удобнее конструктивной по части длины выкладок. И эти примеры Вам уже приводили: дифференциальные уравнения, например. Вы их замучаетесь решать со своими конструктивными заморочками. Зачем, например, ограничиваться вычислимыми числами, если, сняв это ограничение, всё получается намного проще и красивее, а результат остаётся тем же?

[PAV]

Nxx
Вы тут недавно писали, что число $\pi$ считаете "существующим", поскольку его можно вычислить с любой заданной точностью. В связи с этим мне интересно Ваше мнение по поводу следующей конструкции.

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

Это число $x$ также можно вычислить с любой точностью. Запустив алгоритм и наблюдая за его работой, мы будем получать цифры числа $x$ одну за другой. В этом смысле я не считаю это число чем-то принципиально отличающимся от $\pi$. Вы с этим согласны?

[Nxx]

Цитата:

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

В конструктивной математике есть такая теорема:

Пусть функция

$$f(x)$$

определена на отрезке [a,b] и

$$f(a)<0$$

, а

$$f(b)>0$$

. Тогда для любого натурального числа n найдется число c, принадлежащее отрезку [a,b], такое, что

$$f(c)<1/n$$

.

Для практических целей эта теорема имеет точно такую же ценность, что и та, которую ты привел в качестве примера.

Кроме того, если функция

$$f(x)$$

еще и аналитическая, то существует число с, такое, что

$$f(c)=0$$

, то есть,

$$f(c)$$

имеет корень на отрезке [a,b].

[ewert]

Nxx писал(а):

В конструктивной математике есть такая теорема:

Пусть функция

$$f(x)$$

определена на отрезке [a,b] и

$$f(a)<0$$

, а

$$f(b)>0$$

. Тогда для любого натурального числа n найдется число c, принадлежащее отрезку [a,b], такое, что

$$f(c)<1/n$$

.

Ой, напрасно она там есть!