2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 26  След.
 
 
Сообщение05.02.2009, 16:17 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение05.02.2009, 20:33 


04/10/05
272
ВМиК МГУ
Xaositect в сообщении #183831 писал(а):
А есть какие-нибудь основания для такого соблазна? Я как-то не доверяю большим кардиналам Хотя идея за ними довольно интересная.

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


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

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

 Профиль  
                  
 
 
Сообщение05.02.2009, 21:12 


20/07/07
834
gris писал(а):
Nxx писал(а):
... можно потенциально вычислить имеющимися техническими средствами.

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


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

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 15:44 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 18:03 


20/07/07
834
Цитата:
Скорее всего это формально недоказуемо


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

 Профиль  
                  
 
 
Сообщение06.02.2009, 19:39 
Заслуженный участник
Аватара пользователя


28/09/06
10983
Nxx писал(а):
Цитата:
Скорее всего это формально недоказуемо


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

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 21:00 


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

 Профиль  
                  
 
 
Сообщение06.02.2009, 21:15 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Nxx писал(а):
Но таких машин нет в природе и их существование противоречит законам физики.

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 21:18 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 21:27 


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

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

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

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 22:13 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Nxx писал(а):
Цитата:
Это вроде не факт, хотя какие-то физические исследования на эту тему есть.

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

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 23:12 
Заслуженный участник
Аватара пользователя


23/07/05
17989
Москва
Nxx в сообщении #184235 писал(а):
Вполне доказуемо, что вычислить это число на машине Тьюринга нельзя. На машине Тьюринга, снабженной оракулом, способным решать проблему останова - можно. Но таких машин нет в природе и их существование противоречит законам физики.


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

 Профиль  
                  
 
 
Сообщение06.02.2009, 23:22 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Someone писал(а):
Машин Тьюринга вообще нет в природе. Ни с оракулом, ни без оного. Это математическая абстракция.

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

 Профиль  
                  
 
 
Сообщение06.02.2009, 23:26 
Заслуженный участник
Аватара пользователя


23/07/05
17989
Москва
juna в сообщении #184281 писал(а):
Если Вы про бесконечную ленту, то ее можно считать бесконечной потенциально, т.е. увеличивающейся на нужное количество клеток, когда это потребуется.


Нельзя.

 Профиль  
                  
 
 
Сообщение06.02.2009, 23:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 389 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 26  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group