Константа Хайтина для доказательств и в чём невычислимость

[Skipper]

Вот что пишут-

Цитата:

Константа Хайтина, в принципе, может быть использована для решения многих выдающихся проблем теории чисел, включая проблему Гольдбаха и гипотезу Римана. Формулировка проблемы Гольдбаха утверждает, что любое чётное число больше 2 является суммой двух простых. Пусть для заданного чётного числа компьютерная программа ищет соответствующие простые числа. Если гипотеза Гольдбаха верна, программа переходит к следующему чётному числу, и поиск продолжается. Если не существует двух простых чисел, в сумме дающих требуемое чётное число, то программа остановится, найдя контрпример к гипотезе Гольдбаха. Пусть длина этой программы N битов. Если имеются неограниченные ресурсы и время, константа Хайтина может быть использована для доказательства гипотезы Гольдбаха следующим образом. Пусть параллельно запущены все программы длиной N + 1 битов или менее. Если такая N-битная программа останавливается, тогда будет доказано, что гипотеза Гольдбаха неверна. Если же, с другой стороны, достаточное число других программ остановятся, так что ещё одна остановившаяся программа приведет к числу, превышающему константу Хайтина, тогда если программа не остановилась, то она никогда не остановится и гипотеза Гольдбаха будет доказана. Для того, чтобы применить этот метод, нам необходимы лишь первые N битов константы Хайтина.

Та же константа Хайтина может быть использована для доказательства гипотезы Римана и множества других нерешённых проблем математики.

И ещё,

Цитата:

Calude, Dinneen, и Shu вычислили первые 64 бита константы Хайтина для конкретной машины. Вот они, в двоичной записи:
0,0000001000000100000110001000011010001111110010111011101000010000…
и в десятичной записи:
0,0078749969978123844…

Возможность верно вычислить определённую (но не любую) цифру константы Хайтина...

Имеем,
1) возможность вычислить определенную цифру константы Хайтина.
В чём тогда заключается её "невычислимость"? К примеру, выше посчитали цифры константы Хайтина на нужных нам позициях, и благодаря этому можно к примеру, доказать недоказанные ранее гипотезы.
Имеется в виду, что начиная с какой то позиции и дальше вправо, мы не сможем вычислять биты константы Хайтина? То есть точность ограничена.

Или же имеется в виду, что и некая промежуточная цифра константы Хайтина не может быть вычислена,
например в примере выше, 6-я позиция:
$0,00787$ ? $9969978123844$ ?

И в таком случае, нам нельзя получить нужной точности (для данного алгоритма), чтобы используя
константу Хайтина, доказать некоторые недоказанные утверждения (гипотеза Гольдбаха, Римана и т.д.) ?

[dgwuqtj]

Skipper в сообщении #1661697 писал(а):

Имеем,
1) возможность вычислить определенную цифру константы Хайтина.
В чём тогда заключается её "невычислимость"? К примеру, выше посчитали цифры константы Хайтина на нужных нам позициях, и благодаря этому можно к примеру, доказать недоказанные ранее гипотезы.
Имеется в виду, что начиная с какой то позиции и дальше вправо, мы не сможем вычислять биты константы Хайтина? То есть точность ограничена.

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