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

[Утундрий]

Интересен еще и такой вопрос: а существует ли хотя бы одно натуральное невычислимое число?

[маткиб]

juna писал(а):

Введем определение, дьявол - это существо о двух рогах и четырех копытах. Из допущения о его существовании нельзя получить противоречие с законами мироздания, следовательно, он существует.
А теперь становится страшно, ведь теперь действительно существует.

Именно так Вы и рассуждаете.

Не осилил аналогии.

[Nxx]

Цитата:

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

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

Цитата:

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

Это верно только в конструктивистской математике. В классической количество чисел, которые полностью характеризуются каким-либо свойством или набором свойств, счетно. Как и счетно множество всевозможных свойств.

Цитата:

Интересен еще и такой вопрос: а существует ли хотя бы одно натуральное невычислимое число?

Нет, конечно.

[Xaositect]

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

Это верно только в конструктивистской математике. В классической количество чисел, которые полностью характеризуются каким-либо свойством или набором свойств, счетно. Как и счетно множество всевозможных свойств.

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

[Утундрий]

Наверное мой вопрос слишком наивен) Хотя, в моем понимании, чтобы "вычислить" число "стопиццот", его достаточно назвать)

[epros]

Nxx писал(а):

В классической [математике] количество чисел, которые полностью характеризуются каким-либо свойством или набором свойств, счетно.

Правильно ли я понял, что число $x$ "полностью характеризуется" свойством $\varphi$, тогда и только тогда, когда $\exists! r (\varphi(r)) \wedge \varphi(x)$?

А вывод о том, что количество таких чисел счётно, Вы делаете исключительно из того, что множество всех свойств счётно, а стало быть и подмножество свойств, "полностью характеризующих" какое-нибудь число, тоже счётно?

Nxx писал(а):

Как и счетно множество всевозможных свойств.

С чего Вы это взяли? Множество формул теории, которыми записываются свойства, действительно счётно (с точки зрения метатеории). С точки зрения конструктивного анализа также можно утверждать, что "существуют" только такие свойства, которые можно записать формулами. Но с какой стати классическая математика должна утверждать, что множество свойств (включая такие, формула для записи которых нам неизвестна) счётно?

[маткиб]

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

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

Это очень правильно, что Вы сделали поправку в скобках, а то многие тут с умным видом разглагольствуют, как будто устройство мира знают (выделение цветом моё).

[ewert]

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

[epros]

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

а то многие тут с умным видом разглагольствуют, как будто устройство мира знают

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

[ewert]

множество аксиом счётно, в то время как мир континуален (во всяком случае, так принято считать, и никакие опытные факты этому не противоречат). Следовательно, попытка втиснуть мир в аксиомы -- бессмысленна.

[epros]

ewert писал(а):

попытка втиснуть мир в аксиомы -- бессмысленна.

А Вы знаете какие-то другие способы описания мира, кроме теорий, построенных на неких аксиомах?

[Nxx]

ewert писал(а):

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

Че?

Добавлено спустя 1 минуту 26 секунд:

Цитата:

как мир континуален (во всяком случае, так принято считать

Кем принято считать?

[ewert]

Таво. Всеми принято считать.

[Nxx]

ewert писал(а):

Таво. Всеми принято считать.

Пофамильно, если можно.

[ewert]

это долго -- все шесть миллиардов перечислять.

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