Вычисления с бесконечным алфавитом

[epros]

Toucan:

Отделено от темы «Достоверное событие, невозможное событие»

Munin в сообщении #602763 писал(а):

epros в сообщении #602755 писал(а):

Тогда точка 1.5 может быть выбрана.

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

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

[Munin]

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

[epros]

Munin в сообщении #602800 писал(а):

Ага, если определение, принадлежит ли это число диапазону, невычислимо

Мммм, всё не так просто. В частности, я не могу придумать такого определения, чтобы оно:
1) доказанно определяло конкретное число;
2) вопрос его принадлежности диапазону был доказанно алгоритмически неразрешим.

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

[Mathusic]

epros в сообщении #602823 писал(а):

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

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

[Aritaborian]

epros в сообщении #602823 писал(а):

Мммм, всё не так просто.

А что насчёт Busy beaver?

-- 03.08.2012, 18:19 --

Mathusic в сообщении #602826 писал(а):

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

Поддерживаю вопрос.

[epros]

Mathusic в сообщении #602826 писал(а):

epros в сообщении #602823 писал(а):

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

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

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

[Mathusic]

epros в сообщении #602896 писал(а):

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

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

[epros]

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 писал(а):

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

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

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

[Munin]

epros в сообщении #602898 писал(а):

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

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

[epros]

Munin в сообщении #602904 писал(а):

epros в сообщении #602898 писал(а):

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

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

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

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

[Munin]

epros в сообщении #602933 писал(а):

Здесь не разница между типам функций, а разница между функцией и её значением в конкретной точке. Функция, в том числе двузначная, может быть невычислимой.

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

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

[epros]

Munin в сообщении #602938 писал(а):

Но это опять разница между элементами множеств $2$ и $2^{\mathbb{N}}$! А вы говорите, не в этом дело.

Ээээ, как бы выразиться пообразнее.Разница между «знаниями» о конечном и о бесконечном объектах. Значение истинности конкретного утверждения - конечный объект (можно записать «истина» или «ложь»). Каждое конкретное натуральное число - конечный объект (его можно выписать в виде строки цифр). Двузначная функция натурального аргумента - бесконечный объект. Нельзя выписать произвольную функцию в виде таблицы значений.

[Munin]

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

[epros]

Munin в сообщении #602954 писал(а):

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

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

[Munin]

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