2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 8  След.
 
 Вычисления с бесконечным алфавитом
Сообщение03.08.2012, 17:53 
Заслуженный участник
Аватара пользователя


28/09/06
10834
 i  Toucan:
Отделено от темы «Достоверное событие, невозможное событие»


Munin в сообщении #602763 писал(а):
epros в сообщении #602755 писал(а):
Тогда точка 1.5 может быть выбрана.

Вау. Мне кажется, это подкоп под аксиому выбора. Если мы можем выбирать точки не из данного множества... :-)
Если углубиться в формализацию, то да, пожалуй что где-то и так. Хотя в таком случае пример с числом 1.5 - неудачный, ибо всем «очевидно», что оно не принадлежит данному диапазону. Но можно исхитриться придумать определение такого числа, по которому фиг скажешь, принадлежит оно данному диапазону или нет. И вот, допустим, некто «выбрал» это число - т.е. привёл определение и сказал: «я его выбираю». Что на это смогут ответить критики, которые утверждают, что выбор числа вне данного диапазона «невозможен»?

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение03.08.2012, 17:58 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Ага, если определение, принадлежит ли это число диапазону, невычислимо :-)

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


28/09/06
10834
Munin в сообщении #602800 писал(а):
Ага, если определение, принадлежит ли это число диапазону, невычислимо :-)
Мммм, всё не так просто. В частности, я не могу придумать такого определения, чтобы оно:
1) доказанно определяло конкретное число;
2) вопрос его принадлежности диапазону был доказанно алгоритмически неразрешим.

Но легко можно определить такое число, вопрос принадлежности которого диапазону будет практически неразрешим.

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение03.08.2012, 19:11 
Аватара пользователя


14/08/09
1140
epros в сообщении #602823 писал(а):
вопрос принадлежности которого диапазону будет практически неразрешим

Что это значит? :|

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение03.08.2012, 19:19 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
epros в сообщении #602823 писал(а):
Мммм, всё не так просто.
А что насчёт Busy beaver?

-- 03.08.2012, 18:19 --

Mathusic в сообщении #602826 писал(а):
Что это значит?
Поддерживаю вопрос.

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


28/09/06
10834
Mathusic в сообщении #602826 писал(а):
epros в сообщении #602823 писал(а):
вопрос принадлежности которого диапазону будет практически неразрешим

Что это значит? :|
Это значит, что мы не сможем его разрешить, но доказательства алгоритмической неразрешимости у нас тоже не будет.

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение03.08.2012, 23:04 
Аватара пользователя


14/08/09
1140
epros в сообщении #602896 писал(а):
Это значит, что мы не сможем его разрешить, но доказательства алгоритмической неразрешимости у нас тоже не будет.

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

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


28/09/06
10834
Aritaborian в сообщении #602828 писал(а):
А что насчёт Busy beaver?
Он для этого не подойдет. Т.е. можно определить число, скажем
$ x=\sum\limits_{n=5}^{\infty} \frac{1}{\Sigma(n)} - \frac{1}{5000}$
которое будет:
А) гарантированно невычислимым
Б) неизвестно, больше или меньше нуля.

Но дело в том, что невычислимым будет число $x$, а не значение истинности утверждения $x>0$. Согласно классической логике, значение истинности этого утверждения «либо истинно, либо ложно», а значит в обоих из возможных случаев - вычислимо.

-- Сб авг 04, 2012 00:24:59 --

Mathusic в сообщении #602897 писал(а):
epros в сообщении #602896 писал(а):
Это значит, что мы не сможем его разрешить, но доказательства алгоритмической неразрешимости у нас тоже не будет.

То есть, например, если отдать его гипотетическим инопланетянам, у которых вычислительные мощности превосходят наши на порядки, то для них он может быть разрешимым? :?
Совершенно верно. И даже мы сами может быть через пару лет его разрешим. Но пока-то - не можем.

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


30/01/06
72407
epros в сообщении #602898 писал(а):
Согласно классической логике, значение истинности этого утверждения «либо истинно, либо ложно», а значит в обоих из возможных случаев - вычислимо.

А почему настолько различаются роли функций, принимающих значения на $2$ и на $2^{\mathbb{N}}$?

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение04.08.2012, 08:16 
Заслуженный участник
Аватара пользователя


28/09/06
10834
Munin в сообщении #602904 писал(а):
epros в сообщении #602898 писал(а):
Согласно классической логике, значение истинности этого утверждения «либо истинно, либо ложно», а значит в обоих из возможных случаев - вычислимо.

А почему настолько различаются роли функций, принимающих значения на $2$ и на $2^{\mathbb{N}}$?
Здесь не разница между типам функций, а разница между функцией и её значением в конкретной точке. Функция, в том числе двузначная, может быть невычислимой. А вот для значения натурально-значной (а тем более - конечно-значной) функции в конкретной точке в классической логике понятия «невычислимости» нет. Т.е. для $\Sigma(5)$, например, нельзя сказать, что оно невычислимо - оно просто «пока неизвестно».

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

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение04.08.2012, 08:32 
Заслуженный участник
Аватара пользователя


30/01/06
72407
epros в сообщении #602933 писал(а):
Здесь не разница между типам функций, а разница между функцией и её значением в конкретной точке. Функция, в том числе двузначная, может быть невычислимой.

Вот и замените $x>0$ на такую функцию, делов-то.

А, понял, она будет невычислима не в отдельно взятой точке $x_0,$ а как целое... То есть, разница между тем, знаем ли мы функцию в отдельной точке, или сразу на всём бесконечном числе точек. Но это опять разница между элементами множеств $2$ и $2^{\mathbb{N}}$! А вы говорите, не в этом дело.

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение04.08.2012, 09:20 
Заслуженный участник
Аватара пользователя


28/09/06
10834
Munin в сообщении #602938 писал(а):
Но это опять разница между элементами множеств $2$ и $2^{\mathbb{N}}$! А вы говорите, не в этом дело.
Ээээ, как бы выразиться пообразнее.Разница между «знаниями» о конечном и о бесконечном объектах. Значение истинности конкретного утверждения - конечный объект (можно записать «истина» или «ложь»). Каждое конкретное натуральное число - конечный объект (его можно выписать в виде строки цифр). Двузначная функция натурального аргумента - бесконечный объект. Нельзя выписать произвольную функцию в виде таблицы значений.

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


30/01/06
72407
То есть, дело в том, что машина Тьюринга работает с конечным алфавитом?

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение04.08.2012, 09:31 
Заслуженный участник
Аватара пользователя


28/09/06
10834
Munin в сообщении #602954 писал(а):
То есть, дело в том, что машина Тьюринга работает с конечным алфавитом?
Нет. Скорее дело в том, что машина Тьюринга должна закончить свою работу за конечное количество шагов.

 Профиль  
                  
 
 Re: Достоверное событие, невозможное событие
Сообщение04.08.2012, 10:01 
Заслуженный участник
Аватара пользователя


30/01/06
72407
А. Вона что. Кстати, это интересно, а если позволить бесконечный алфавит, это будет то же самое, что позволить бесконечное число шагов, или нет?.. :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 115 ]  На страницу 1, 2, 3, 4, 5 ... 8  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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