Константа Хайтина

[venco]

Темa, в которой всплыла константа Хайтина, пошла в пургаторий, но мне всё-таки хочется разобраться в этом.
Итак, константа Хайтина приводится как пример неконструктивного числа. Мне же непонятно, можно ли вообще причислять эту сущность к числам?
Если пытаться трактовать её как число, то про неё можно лишь сказать, что она больше всех чисел $\le R_{min}$ и меньше всех чисел $\ge R_{max}$. И ничего нелься сказать про отношение к числам из интервала $(R_{min},R_{max})$.
Хотя, с другой стороны, комплексные числа тоже нельзя упорядочить, но ведь в данном случае мы говорим о действительных числах, для которых порядок определен.

[Someone]

Вообще, насколько я понял, это не одна какая-то константа, а величина, зависящая от принятого кодирования функций.

[venco]

Someone в сообщении #406006 писал(а):

Вообще, насколько я понял, это не одна какая-то константа, а величина, зависящая от принятого кодирования функций.

Это да, но мы рассмотрим какую-нибудь одну, для некоего определённого кодирования. Проблема не в этом.

[Someone]

А в чём?

[venco]

Someone в сообщении #406037 писал(а):

А в чём?

В том, что даже для заданного кодирования константа определена с точностью до некоего интервала. Т.е. она не сравнима с числами в этом интервале. Имеет ли право этот объект именоваться числом?

[Xaositect]

venco в сообщении #406055 писал(а):

В том, что даже для заданного кодирования константа определена с точностью до некоего интервала. Т.е. она не сравнима с числами в этом интервале. Имеет ли право этот объект именоваться числом?

А это Вы в каком источнике читаете? Просто вроде бы со строгими сравнениями как раз не должно быть ничего страшного.

[venco]

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

А это Вы в каком источнике читаете?

Википедия и MathWorld.

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

Просто вроде бы со строгими сравнениями как раз не должно быть ничего страшного.

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

[Xaositect]

Я там что-то не вижу $R_{\min}$, $R_{\max}$, ткните меня носом.

Понятно, что если мы признаем числами только конструктивные числа, то константы Чейтина нет и вопрос о ее сравнении с чем то бессмыслен.

Но если у нас есть конструктивные числа и алгоритм их сравнения, который выдает >, < или зацикливается, когда они равны, и есть оракул, выдающий биты константы Чейтина, то мы вполне можем сравнить этот оракул с любым конструктивным числом и получить > или <, так как по определению она от любого конструктивного числа отлична.

[venco]

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

Я там что-то не вижу $R_{\min}$, $R_{\max}$, ткните меня носом.

Это я ввёл - просто границы интервала в котором должна находиться константа Хайтина.

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

Понятно, что если мы признаем числами только конструктивные числа, то константы Чейтина нет и вопрос о ее сравнении с чем то бессмыслен.

Вот и я об этом.

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

Но если у нас есть конструктивные числа и алгоритм их сравнения, который выдает >, < или зацикливается, когда они равны, и есть оракул, выдающий биты константы Чейтина, то мы вполне можем сравнить этот оракул с любым конструктивным числом и получить > или <, так как по определению она от любого конструктивного числа отлична.

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

[Xaositect]

venco в сообщении #406080 писал(а):

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

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

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

Btw, она рекурсивно-перечислима слева, так что существует алгоритм, который по конструктивному числу выдает <, если оно меньше константы Чейтина, а в остальных случаях зацикливается.

[Someone]

venco в сообщении #406067 писал(а):

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

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

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

[venco]

Someone в сообщении #406097 писал(а):

Если не останавливается, то единичку не добавим.

Так ведь не в каждом случае мы можем определить, что алгоритм не останавливается.

-- Пт янв 28, 2011 16:16:50 --

Someone в сообщении #406097 писал(а):

Алгоритм либо останавливается, либо не останавливается.

Или Вы имеете в виду, что хоть мы и не можем узнать, остановится алгоритм или нет, тем не менее это свойство алгоритма определено?
Насколько я понимаю, одно из следствий теоремы Гёделя как раз в том, что оба варианта (остановится или нет) могут не противоречить выбранным аксиомам. Более того, в таких случаях можно добавить ещё одну аксиому, причём двумя противоложными способами, и в результате задача об остановке данного алгоритма будет решена. Из этого можно сделать вывод, что в любой конечной аксиоматике константа Хайтина по настоящему не определена, а не просто не вычислима. Т.е. мы можем непротиворечиво дополнить аксиоматику двумя способами для каждого такого неопределимого бита, так что значение константы Хайтина будет разным, но по прежнему неопределимым, т.к. дальше встретятся ещё неопределимые биты, которые, в свою очередь, тоже можно определить двумя способами, добавив ещё одну аксиому, и т.д.

[Someone]

venco в сообщении #406106 писал(а):

Так ведь не в каждом случае мы можем определить, что алгоритм не останавливается.

Если бы могли, то константа была бы вычислимой.

Ещё раз. Решение вопроса об остановке алгоритма может зависеть от модели арифметики. В таком случае нельзя доказать ни то, что алгоритм останавливается, ни то, что он не останавливается, поскольку все аксиомы теории выполняются во всех моделях. Однако в каждой модели константа Хайтина имеет вполне определённое значение. Просто в разных моделях эти значения разные.

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

[venco]

Someone в сообщении #406118 писал(а):

Утверждение, что каждый алгоритм (при заданных исходных данных) либо останавливается, либо не останавливается, считается справедливым и в конструктивном рекурсивном анализе (принцип Маркова).

Т.е. вот это:

venco в сообщении #406106 писал(а):

Насколько я понимаю, одно из следствий теоремы Гёделя как раз в том, что оба варианта (остановится или нет) могут не противоречить выбранным аксиомам. Более того, в таких случаях можно добавить ещё одну аксиому, причём двумя противоложными способами, и в результате задача об остановке данного алгоритма будет решена.

неверно?

[Someone]

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