А что насчёт Busy beaver?
Он для этого не подойдет. Т.е. можно определить число, скажем
которое будет:
А) гарантированно невычислимым
Б) неизвестно, больше или меньше нуля.
Но дело в том, что невычислимым будет число
, а не значение истинности утверждения
. Согласно классической логике, значение истинности этого утверждения «либо истинно, либо ложно», а значит в обоих из возможных случаев - вычислимо.
-- Сб авг 04, 2012 00:24:59 --Это значит, что мы не сможем его разрешить, но доказательства алгоритмической неразрешимости у нас тоже не будет.
То есть, например, если отдать его гипотетическим инопланетянам, у которых вычислительные мощности превосходят наши на порядки, то для них он может быть разрешимым?
Совершенно верно. И даже мы сами может быть через пару лет его разрешим. Но пока-то - не можем.