Предположение Гольдбаха и численность занятого бобра?

Справочная информация: я полный дилетант в области компьютерных наук.

Я читал о занятых номерах Бивер здесь , и я нашел следующий отрывок:

Человечество может никогда не узнать значение BB (6) наверняка, не говоря уже о значении BB (7) или любом более высоком числе в последовательности.

На самом деле, уже пятеро и шесть претендентов на правила не могут нас понять: мы не можем объяснить, как они «работают» в человеческом смысле. Если творчество наполняет их дизайн, это не потому, что люди вкладывают его в это. Один из способов понять это - даже маленькие машины Тьюринга могут кодировать глубокие математические задачи. Возьмите гипотезу Гольдбаха, что каждое четное число 4 или выше является суммой двух простых чисел: 10 = 7 + 3, 18 = 13 + 5. Эта гипотеза не поддается доказательству с 1742 года. Тем не менее, мы могли бы разработать машину Тьюринга с, скажем, 100 правилами, которая проверяет каждое четное число, чтобы увидеть, является ли оно суммой двух простых чисел, и останавливается, когда и если она находит контрпример к гипотеза. Тогда, зная BB (100), мы могли бы в принципе запустить эту машину для шагов BB (100), решить, останавливается ли она, и таким образом разрешить гипотезу Гольдбаха.

Ааронсон, Скотт. "Кто может назвать большее число?" Кто может назвать большее число? Np, nd Web. 25 ноября 2016 г.

Мне кажется, что автор предполагает, что мы можем доказать или опровергнуть гипотезу Гольдбаха, утверждение о бесконечном числе чисел, в конечном числе вычислений. Я что-то пропустил?

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

Неожиданность может возникнуть из-за (ложного) предположения о том, что поиск BB (100) будет «теоретически более простой» проблемой, которую невозможно сделать только по практическим соображениям - поскольку существует очень много машин, и они могут работать в течение такого длительного времени до остановки если вообще - в конце концов, они просто машины ...

Правда в том, что обнаружение BB (n) для достаточно большого n должно быть непреодолимой задачей как по теоретическим, так и по практическим причинам.

Идея автора состояла в том, что вы можете написать программу из 100 строк (любое фиксированное конечное число здесь), которая выполняет следующее: принимает число x, проверяет гипотезу. Если это не так, тогда остановите, продолжайте на следующем номере.

Зная номер занятого бобра, вы можете смоделировать эту машину для этого количества шагов, а затем решить, останавливается она или нет. Сверху, если он останавливается - гипотеза не верна, если не останавливается - гипотеза верна.

Ааронсон недавно подробно рассказал об этой идее размышления / работе здесь с Едидией. [1] они находят явный конечный автомат 4888 для гипотезы Гольдбаха. Вы можете прочитать статью, чтобы увидеть, как она была построена. ТМ создаются редко, но те, которые раньше были подобны компилятору, основаны на языках высокого уровня, и компиляторы добавляют много состояний. ТМ «ручной сборки» может легко использовать на порядок меньшее количество состояний, например, в сотнях или меньше 100. Другими словами, в этой статье на самом деле не было попыток действительно минимизировать # состояний , общая идея обоснована, и компьютерные ученые, как правило, не очень беспокоятся о точных константах в прикладной работе.

эта общая теория изложена Калудесом (также цитируемым в [1]) в двух превосходных работах, в которых излагаются некоторые теоремы о длинном фольклоре в этой области и которые отмечены другими авторами (например, Мишелем). [2] [ 3] практически любая открытая математическая задача может быть преобразована в неразрешимые задачи. это связано с тем, что большинство математических задач включают поиск бесконечного числа случаев для контрпримеров, а контрпримеры алгоритмически проверяемы (но могут быть неэффективными или требуют больших ТМ и т. д.).

Кроме того, «очень маленькие» ТМ (считаются в # состояниях) могут проверять / быть эквивалентными очень сложным математическим задачам. Например, приблизительная оценка ТМ для разрешения гипотезы Коллатца будет состоять из нескольких десятков состояний.

поэтому существует интересная связь / аналогия между неразрешимостью и полнотой NP. NP - класс эффективно проверяемых задач, то есть экземпляры могут быть проверены за время P. Неразрешимые проблемы - это класс всех задач, которые допускают алгоритмическую проверку контрпримеров без ограничения эффективности.

Вот основной способ понять связь с проблемой занятого бобра. все неразрешимые проблемы эквивалентны из-за вычислимости / эквивалентности по Тьюрингу. подобно тому, как все задачи с полным NP могут быть преобразованы друг в друга за время P (сокращения), все неразрешимые проблемы эквивалентны из-за полноты по Тьюрингу и вычислимых сокращений (что может занять произвольное время). следовательно, проблема занятого бобра в этом смысле эквивалентна проблеме остановки, и если можно решить занятого бобра, то можно решить все открытые математические вопросы.

[1] Относительно небольшая ТМ, поведение которой не зависит от теории множеств / Едидиа, Ааронсон

[2] Оценка сложности математических задач: Часть 1 / Calude

[3] Оценка сложности математических задач: часть 2 / Calude

1. Гипотеза Гольдбаха может быть сфальсифицирована (если на самом деле ложной) такой программой ТМ; это не может быть доказано правильно таким способом (однако, проницательный математик мог бы сделать это).

2. Знание BB (27) позволит в какой-то момент остановить поиск Гольдбаха; тем не менее, ВВ (27) (или Омега Чейтина (27)) ранее потребовалось узнать, останавливается ли Goldbach TM или нет.

Поэтому вводить в заблуждение слова «ВВ (27) включает ответ Гольдбаху»). Хотя это так, более важно то, что «Гольдбах (и многие другие) являются предпосылками для числа ВВ (27)», иными словами, не существует такой вещи, как «функция ВВ», которую вы оспариваете в 27 лет. просто запусти все 27 состояний машин, инкл. Гольдбах и только по факту см. ББ (27). И из практического POV, даже BB (6) кажется неуловимым.

Я думаю, что это менее загадочно, если мы переформулируем точку зрения Ааронсона с точки зрения доказательств:

$C$$C$$C$$C$

$C$$C$$n$$BB(n)$$C = O(BB(n))$