Numery hipotez Goldbacha i Busy Beaver?

Tło: Jestem kompletnym laikiem w dziedzinie informatyki.

Czytałam o numerach Busy Beaver tutaj i znalazłem następujący fragment:

Ludzkość może nigdy nie poznać wartości BB (6) na pewno, nie mówiąc już o wartości BB (7) lub jakiejkolwiek większej liczbie w sekwencji.

Rzeczywiście, wymyka się nam już pierwsza piątka i szóstka rządzących: nie możemy wyjaśnić, jak „działają” w kategoriach ludzkich. Jeśli kreatywność przenika ich projekt, to nie dlatego, że ludzie je tam umieszczają. Jednym ze sposobów na zrozumienie tego jest to, że nawet małe maszyny Turinga mogą kodować głębokie problemy matematyczne. Weźmy hipotezę Goldbacha, że ​​każda liczba parzysta 4 lub wyższa jest sumą dwóch liczb pierwszych: 10 = 7 + 3, 18 = 13 + 5. Przypuszczenie opiera się dowodom od 1742 r. Jednak moglibyśmy zaprojektować maszynę Turinga z, powiedzmy 100 regułami, która testuje każdą liczbę parzystą, aby sprawdzić, czy jest to suma dwóch liczb pierwszych, i zatrzymuje się, gdy i jeśli znajdzie kontrprzykład przypuszczenie. Znając BB (100), moglibyśmy zasadniczo uruchomić tę maszynę dla kroków BB (100), zdecydować, czy się zatrzyma, a tym samym rozwiązać hipotezę Goldbacha.

Aaronson, Scott. „Kto może nazwać większy numer?” Kto może nazwać większą liczbę? Np, i Web. 25 listopada 2016 r.

Wydaje mi się, że autor sugeruje, że możemy udowodnić lub obalić hipotezę Goldbacha, stwierdzenie o nieskończenie wielu liczbach, w skończonej liczbie obliczeń. Czy coś mi brakuje?

To stwierdzenie dotyczy nieskończenie wielu liczb, ale jego wykazanie (lub obalenie) musiałoby być skończonym ćwiczeniem. Jeśli to możliwe.

Zaskoczenie może wynikać z (fałszywego) założenia, że ​​znalezienie BB (100) byłoby problemem „teoretycznie łatwiejszym”, niemożliwym tylko ze względów praktycznych - ponieważ jest tak wiele maszyn i mogą one działać tak długo, zanim się zatrzymają. , jeśli w ogóle - w końcu to tylko maszyny ...

Prawda jest taka, że ​​odkrycie BB (n), dla n wystarczająco dużych, musi być nie do pokonania, zarówno z powodów teoretycznych, jak i praktycznych.

Pomysł autora polegał na tym, że możesz napisać program w 100 liniach (tutaj dowolna stała liczba skończona), który wykonuje następujące czynności: przyjmuje liczbę x, testuje hipotezę. Jeśli nie jest prawdą, zatrzymaj się, kontynuuj od następnego numeru.

Znając liczbę zajętych bobrów, możesz symulować maszynę dla tej liczby kroków, a następnie zdecydować, czy się zatrzyma, czy nie. Z góry, jeśli się zatrzyma - przypuszczenie nie jest prawdą, jeśli się nie zatrzyma - przypuszczenie jest prawdą.

Aaronson ostatnio szczegółowo rozwinął tę myśl / pomysł, współpracując z Yedidią. [1] znajdują jawną maszynę stanu 4888 dla hipotezy Goldbacha. możesz przeczytać artykuł, aby zobaczyć, jak został zbudowany. Bazy TM są rzadko konstruowane, ale te, które zwykle były podobne do kompilatorów w oparciu o języki wysokiego poziomu, a kompilatory dodają wiele stanów. „ręcznie zbudowana” TM mogłaby z łatwością użyć rzędu stanów o mniejszej liczbie stanów, np. w 100s lub mniej niż 100. innymi słowy, tak naprawdę nie było w tym artykule próby naprawdę zminimalizowania liczby stanów . ogólna idea jest solidna, a informatycy generalnie nie martwią się dokładnymi stałymi w pracy.

tę ogólną teorię przedstawili Caludes (cytowani również przez [1]) w dwóch doskonałych pracach, które przedstawiają niektóre twierdzenia o folklorze w tej dziedzinie i które zostały odnotowane przez innych autorów (np. Michela). [2] [ 3] w zasadzie każdy otwarty problem matematyczny można przekształcić w problemy nierozstrzygalne. dzieje się tak, ponieważ większość problemów matematycznych polega na wyszukiwaniu nieskończonej liczby przypadków dla kontrprzykładów, a kontrprzykłady są sprawdzalne algorytmicznie (ale być może nieefektywne lub wymagające dużych baz TM itp.).

również „bardzo małe” bazy TM (liczone w liczbie stanów) mogą sprawdzać / być równoważne bardzo złożonymi problemami matematycznymi. np. przybliżony szacunek dla TM, aby rozwiązać hipotezę collatz, to kilkadziesiąt stanów.

istnieje więc interesujący związek / analogia między nierozstrzygalnością a kompletnością NP. NP to klasa sprawnie sprawdzalnych problemów, tzn. Instancje można sprawdzić w czasie P. nierozstrzygalne problemy są klasą wszystkich problemów, które umożliwiają algorytmiczne sprawdzanie kontrpróbek bez ograniczenia wydajności.

oto podstawowy sposób na zrozumienie związku z problemem zajętego bobra. wszystkie nierozstrzygalne problemy są równoważne ze względu na obliczalność / równoważność Turinga. podobnie jak wszystkie problemy NP zupełne mogą być konwertowane na siebie w czasie P (redukcje), wszystkie nierozstrzygalne problemy są równoważne ze względu na kompletność Turinga i redukcje obliczeniowe (które mogą zająć dowolny czas). stąd problem zajętego bobra jest w tym sensie równoważny problemowi zatrzymania, a jeśli można rozwiązać zajęty bobra, można rozwiązać wszystkie otwarte pytania matematyczne.

[1] Stosunkowo mała TM, której zachowanie jest niezależne od teorii mnogości / Yedidia, Aaronson

[2] Ocena złożoności problemów matematycznych: część 1 / Calude

[3] Ocena złożoności problemów matematycznych: część 2 / Calude

1. Hipoteza Goldbacha może zostać sfałszowana (jeśli faktycznie fałszywa) przez taki program TM; w ten sposób nie można udowodnić, że jest poprawny (jednak wnikliwy matematyk może to zrobić).

2. Znajomość BB (27) pozwoliłaby w pewnym momencie przerwać poszukiwania Goldbacha; niemniej jednak BB (27) (lub Omega Chaitin (27)) będzie wcześniej wymagał wiedzieć, czy Goldbach TM ostatecznie się zatrzyma, czy nie.

Dlatego mylące jest twierdzenie, że „BB (27) zawiera odpowiedź dla Goldbacha”. Chociaż tak się dzieje, bardziej chodzi o to, że: „Goldbach (i wiele innych) jest warunkiem wstępnym liczby BB (27)”, innymi słowy, nie ma czegoś takiego jak „funkcja BB”, której rzucasz wyzwanie w wieku 27 lat. po prostu uruchom wszystkie 27-stanowe maszyny, inkl. Goldbach, a dopiero po fakcie zobacz BB (27). A z praktycznego POV nawet BB (6) wydaje się nieuchwytny.

Myślę, że to mniej tajemnicze, jeśli powtórzymy punkt Aaronsona pod względem dowodów:

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

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