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

[hurtsy]

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

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

Есть еще вариант, считать её суммой константы-числа и константы случайной величины. А что, есть примеры успешного применения Константы Хайтина для математических задач? С уважением,

[Dandan]

Я думаю всё это можно объяснить намного проще, такие сложные конструкции как константа Хайтина совершенно не нужны.

Вот допустим у нас есть некий алгоритм (будем считать, что он не принимает ничего на вход). Мы его можем запустить. Тогда существуют всего лишь 2 возможности:
1. Либо он когда-нибудь остановится
2. Либо он никогда не остановится

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

Однако, нам ничего не мешает по алгоритму $A$ определить число $\phi_A$, которое равно 1 если будет 1й случай и равно 0 если будет 2й случай.

Я не вижу в определении числа $\phi_A$ каких-то нарушений, как по мне, это абсолютно ясно определенное и "существующее в реальности" число.

[epros]

Dandan в сообщении #406291 писал(а):

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

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

Вообще, насколько я знаю, никто пока не придумал как определить "вычислимость" для отдельных натуральных чисел.