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

[Nxx]

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

http://dxdy.ru/post185188.html#185188

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

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

Цитата:

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

Ну и чем это отличается от функции, которая принимает значение 1, если гипотеза Римана не верна?

[Someone]

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

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

Только конструктивисты советской школы считают, что вычислимость означает механическую вычислимость по заранее написанной программе.

[маткиб]

Nxx писал(а):

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

Я такого не утверждал. Я утверждал, что та функция, которую Вы определили, вычислима.

А что значит "алгоритм для решения гипотезы Римана", я не понимаю. Говорить о существовании алгоритмов имеет смысл только когда речь идёт о массовой проблеме, т.е. о проблеме с параметром, а гипотеза Римана - это одиночная проблема, у которой ответ - либо "да", либо "нет". Поэтому с Вас определение, что значит "алгоритм A решает гипотезу Римана".

[Nxx]

Цитирую вас:

Цитата:

Не знаю, как там у конструктивистов, а у нормальных математиков функция называется вычислимой, если существует алгоритм, который её вычисляет.

Вы утверждаете, что функция, выдающая 0 если гипотеза Римана верна и 1 если не верна, вычислима. С вас алгоритм или доказательство его существования. Если вам обязательно нужен параметр, то вот:

$$ f(x)=\begin{cases} x,\text{ если гипотеза Римана верна} \\ 0,\text{ если гипотеза Римана не верна}\end{cases} $$

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

[epros]

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

не исключено, что своими конструктивными терминами Вы даже сформулировать задачу не сможете в таком виде, в каком она решение будет иметь.

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

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

Если теория прикладная, то проверять по-любому придётся. Вы же не знаете, какие функции в реальном мире бывают, а какие нет, придётся опытным путём выяснять. Вдруг и разрывные есть?

Интересно, каким образом в реальном мире Вы отличите разрывную функцию от просто очень быстро меняющейся на данном отрезке?

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

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

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

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

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

А я видел массу полезных, примеры выше.

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

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

Это называется "правильная постановка задачи". Конструктивный/неконструктивный подход - это относится уже к способу её решения.

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

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

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

Воображение у Вас слишком богатое. Что ещё тут можно сказать? Если Вы постулируете, что на все вопросы у кого-то есть правильные и однозначные ответы, то Вы таким образом накладываете ограничение на свою способность сформулировать действительно сложный вопрос.

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

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

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

[маткиб]

Nxx писал(а):

Цитирую вас:

Цитата:

Не знаю, как там у конструктивистов, а у нормальных математиков функция называется вычислимой, если существует алгоритм, который её вычисляет.

Вы утверждаете, что функция, выдающая 0 если гипотеза Римана верна и 1 если не верна, вычислима. С вас алгоритм или доказательство его существования. Если вам обязательно нужен параметр, то вот:

$$ f(x)=\begin{cases} x,\text{ если гипотеза Римана верна} \\ 0,\text{ если гипотеза Римана не верна}\end{cases} $$

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

Блин, я же приводил Вам доказательство. Могу ещё раз: пусть $A$ - гипотеза Римана, $B$ - утверждение о вычислимости $f(x)$. Если $A$, то $f(x)=x$ => вычислима (вычисляется стандартным алгоритмом, который генерирует $x$), т.е. $A\rightarrow B$, если $\neg A$, то $f(x)=0$ => тоже вычислима, т.е. $\neg A\rightarrow B$. Я надеюсь, Вы не будете отрицать, что в классической математике выполняется

$$ ((A\rightarrow B)\&(\neg A\rightarrow B))\rightarrow B $$

?
Откуда и выводим $B$.
Очень надеюсь, что Вы не тролль и реально не понимаете, а не провоцируете.

[Nxx]

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

Блин, я же приводил Вам доказательство. Могу ещё раз: пусть $A$ - гипотеза Римана, $B$ - утверждение о вычислимости $f(x)$. Если $A$, то $f(x)=x$ => вычислима (вычисляется стандартным алгоритмом, который генерирует $x$), т.е. $A\rightarrow B$, если $\neg A$, то $f(x)=0$ => тоже вычислима, т.е. $\neg A\rightarrow B$. Я надеюсь, Вы не будете отрицать, что в классической математике выполняется

$$ ((A\rightarrow B)\&(\neg A\rightarrow B))\rightarrow B $$

?
Откуда и выводим $B$.
Очень надеюсь, что Вы не тролль и реально не понимаете, а не провоцируете.

Доказательство, что А вычислимо в студию. Иначе у вас получается, что вообще все функции вычислимы, включая, например, число омега.

[маткиб]

epros писал(а):

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

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

epros писал(а):

Интересно, каким образом в реальном мире Вы отличите разрывную функцию от просто очень быстро меняющейся на данном отрезке?

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

epros писал(а):

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

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

epros писал(а):

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

У Вас очень упрощённое представление о реальности (хотя это уже оффтоп).

epros писал(а):

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

А я видел массу полезных, примеры выше.

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

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

epros писал(а):

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

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

epros писал(а):

Воображение у Вас слишком богатое. Что ещё тут можно сказать? Если Вы постулируете, что на все вопросы у кого-то есть правильные и однозначные ответы, то Вы таким образом накладываете ограничение на свою способность сформулировать действительно сложный вопрос.

Для кого сложный?

epros писал(а):

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

Я не спорю с тем, что sign невычислима (в том смысле), только лично мне это не мешает.

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

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

Доказательство, что А вычислимо в студию.

Это не требуется - раз.
Определение вычислимости для утверждения - два.

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

Иначе у вас получается, что вообще все функции вычислимы, включая, например, число омега.

Доказательство?

[Nxx]

Цитата:

Это не требуется - раз.

Требуется.

Цитата:

Определение вычислимости для утверждения - два.

Такое же как и для числа или функции.

Цитата:

Доказательство?

Доказательство в вашем стиле, что омега вычислима:

У омеги в двоичном разложении n-й разряд равен N. N равно 0 или 1. Пусть А - утверждение, что N равно 0. Если А истинно, пишем 0, иначе пишем 1. Значит, омега вычислима. Вот ваше рассуждение.

[маткиб]

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

Такое же как и для числа или функции.

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

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

Доказательство в вашем стиле, что омега вычислима:

У омеги в двоичном разложении n-й разряд равен N. N равно 0 или 1. Пусть А - утверждение, что N равно 0. Если А истинно, пишем 0, иначе пишем 1. Значит, омега вычислима. Вот ваше рассуждение.

Существование алгоритма для выделенного красным не очевидно. С Вас этот алгоритм.

Замечание: то, что выделенно красным, - это задача с параметром (N), поэтому говорить о существовании алгоритма имеет смысл. Если бы A было одиночным утверждением, то истинность A можно было бы забить в программу машины Тьюринга, тогда никаких проблем бы не было.

[Xaositect]

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

Доказательство в вашем стиле, что омега вычислима:

У омеги в двоичном разложении n-й разряд равен N. N равно 0 или 1. Пусть А - утверждение, что N равно 0. Если А истинно, пишем 0, иначе пишем 1. Значит, омега вычислима. Вот ваше рассуждение.

Есть большая разница между тем и этим рассуждением.
1. Если

$$A$$

, то

$$f$$

вычислима. Если

$$\neg A$$

, то

$$f$$

вычислима. Значит,

$$f$$

вычислима.
Здесь мы доказываем существование алгоритма. Неконструктивно, т.е. самого алгоритма не предъявляя.
2. Пусть

$$A_i \equiv (f(i) = 1)$$

Если

$$A_i$$

, то

$$f(i) = 1$$

. Если

$$\neg A_i$$

, то

$$f(i) = 0$$

.
Тут никаких алгоритмов нет и в помине. Оно и так ясно, что

$$A\equiv A$$

и чтобы вычислить

$$f(i)$$

, его надо вычислить.

[Nxx]

Цитата:

Замечание: то, что выделенно красным, - это задача с параметром (N), поэтому говорить о существовании алгоритма имеет смысл. Если бы A было одиночным утверждением, то истинность A можно было бы забить в программу машины Тьюринга, тогда никаких проблем бы не было.

Как по-вашему, тысячный знак омеги вычислим? Вот конкретное одиночное утверждение: "тысячный знак омеги равен нулю".

[маткиб]

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

Как по-вашему, тысячный знак омеги вычислим?

Вычислим (ибо константа).

[Nxx]

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

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

Как по-вашему, тысячный знак омеги вычислим?

Вычислим (ибо константа).

Ну так Омега тоже константа - значит, вычислима?

...Итак, 1000-й вычислим, 1001-й вычислим, 1002-й вычислим, я правильно понял? Любой разряд Омеги вычислим, так?

[epros]

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

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

Да ладно, какие такие проблемы?

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

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

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

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

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

Не сомневаюсь только при вполне определённых обстоятельствах: когда процедура поиска решения заведомо конечна, а значит, закончив её, мы попадаем в то самое состояние, когда "решение либо есть, либо нет".

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

Классические же математики обобщают это и на "бесконечные" сущности (а чем они хуже?)

Да всего лишь только тем, что они не "сущности", а "выдуманности".

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

У Вас очень упрощённое представление о реальности (хотя это уже оффтоп).

А по-моему это у Вас очень идеализированные представления о реальности (получившийся каламбур сам по себе примечателен).

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

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

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

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

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

Для кого сложный?

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

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

Я не спорю с тем, что sign невычислима (в том смысле), только лично мне это не мешает.

Мне тоже не мешает. Просто с точки зрения конструктивного анализа то, что невычислимо, не есть "функция". Ибо функция - это отображение чего-то куда-то, а какое же это "отображение", если вот пример конкретного объекта, который никак никуда не может "отобразиться"?