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

[Xaositect]

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

А ещё возникает соблазн к таким важным прикладным проблемам, как, например, P?=NP - проблема, применить какие-нибудь крутые аксиомы бесконечности, типа существования кардинала Mahlo (и не факт, что для решения этой проблемы хватит ZFC, и уж тем более арифметики второго порядка, хотя сформулировать её можно и на языке обычной арифметики первого порядка).

А есть какие-нибудь основания для такого соблазна? Я как-то не доверяю большим кардиналам Хотя идея за ними довольно интересная.
Еще проблему P-NP с гипотезой Римана пытаются связать.

[маткиб]

Xaositect в сообщении #183831 писал(а):

А есть какие-нибудь основания для такого соблазна? Я как-то не доверяю большим кардиналам Хотя идея за ними довольно интересная.

Еще проблему P-NP с гипотезой Римана пытаются связать.

Основание пока только одно: большие кардиналы кое-что дают для формальной арифметики (поэтому может быть и в этом случае дадут).

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

[Nxx]

gris писал(а):

Nxx писал(а):

... можно потенциально вычислить имеющимися техническими средствами.

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

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

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

[epros]

Nxx писал(а):

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

Nxx, не будьте столь категоричны: Скорее всего это формально недоказуемо (хотя по здравому смыслу это так).

Кстати, невозможность пронумеровать вычислимые числа конструктивно доказуема (хотя есть разница между "возможностью пронумеровать" в конструктивном смысле и "существованием биекции с $\mathbb{N}$" в теоретико-множественном смысле).

[Nxx]

Цитата:

Скорее всего это формально недоказуемо

Что именно недоказуемо?

[epros]

Nxx писал(а):

Цитата:

Скорее всего это формально недоказуемо

Что именно недоказуемо?

Вот это:

Nxx писал(а):

что вычислить это число невозможно (как и проверить, то ли число мы вычислили, которое искали)

[Nxx]

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

[Xaositect]

Nxx писал(а):

Но таких машин нет в природе и их существование противоречит законам физики.

Это вроде не факт, хотя какие-то физические исследования на эту тему есть.

[epros]

Nxx писал(а):

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

Интересно, а как Вы вообще определите состояние "вычислена омега"? Вот я знаю, что нельзя вычислить "маскимальное натуральное число" (это легко доказуемо). Но оно - не омега.

[Nxx]

Цитата:

Это вроде не факт, хотя какие-то физические исследования на эту тему есть.

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

Цитата:

Интересно, а как Вы вообще определите состояние "вычислена омега"? Вот я знаю, что нельзя вычислить "маскимальное натуральное число" (это легко доказуемо). Но оно - не омега.

Речь идет о вычислении с любой заданной точностью.

[Xaositect]

Nxx писал(а):

Цитата:

Это вроде не факт, хотя какие-то физические исследования на эту тему есть.

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

Насколько я понимаю, утверждение о физической реализуемости оракула для задачи останова есть несколько ослабленный вариант тезиса Черча-Тьюринга. А с этим тезисом не все ясно: практически все в него верят, но достаточно полного физического обоснования, вроде бы, нет. Я интересовался этим вопросом несколько лет назад, возможно, с тех пор что-то изменилось.

[Someone]

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

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

Машин Тьюринга вообще нет в природе. Ни с оракулом, ни без оного. Это математическая абстракция.

[juna]

Someone писал(а):

Машин Тьюринга вообще нет в природе. Ни с оракулом, ни без оного. Это математическая абстракция.

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

[Someone]

juna в сообщении #184281 писал(а):

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

Нельзя.

[juna]

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