Jakie jest jasne wyjaśnienie uniwersalnego wyszukiwania?

Czytam książkę na temat informatyki, ale brakuje mi wstępnych podstaw. Zwykle, gdy spotykam się z terminami, nie rozumiem, że po prostu je wyszukuję, ale dla Universal Search po prostu nie byłem w stanie znaleźć wyjaśnienia odpowiedniego dla czytelnika bez doświadczenia w statystyce / informatyce.

Czytałem ten artykuł o Universal Search z Scholarpedia , który wydaje się obejmować ten temat. Byłbym wdzięczny za wyjaśnienie, co oznacza Universal Search (lub Levin Search ).

Pomyśl o tym w ten sposób. Masz problem z wejściem i wiesz, jak zweryfikować rozwiązanie, jeśli kiedykolwiek je znalazłeś (np. Odwrotność macierzy lub cokolwiek, co chciałbyś sobie wyobrazić).$x$

Teraz weź swój ulubiony język programowania (powiedzmy Python) i stwórz każdy program w języku Python składający się maksymalnie z 10 znaków! Następnie uruchamiasz wszystkie te programy z wejściem przez 10 sekund każdy, każdy na wejściu . Jeśli żaden z nich nie udzieli odpowiedzi, przejdziesz do 11. Uruchom każdy program składający się maksymalnie z 11 znaków (łącznie z tymi, które już wypróbowałeś) przez 11 sekund każdy na wejściu . Jeśli żaden z nich nie poda poprawnej odpowiedzi, kontynuujesz do 12 i tak dalej.$x$$x$

Bardziej formalnie, w iteracji , uruchamiasz wszystkie programy o długości co najwyżej (ostatecznie wiele, ale oczywiście wykładniczo w ), każdy na sekundy (lub kroki).ja ja $i$$i$$i$$i$

Jest to program, powiedzmy , który daje poprawny wynik w sekund. Kiedy dojdziesz do iteracji , ten program będzie działał przez co najmniej sekund, a ty wypiszesz i rozwiązanie.$P$$s$$i = \max\{|P|, s\}$$s$$P$

Aby dodać do tego, co powiedział Pål GD, pamiętaj, że uruchamiasz wszystkie programy o długości lub mniejszej i pozwalasz im działać przez co najwyżej sekundy. Możliwe, że istnieje program, który uzyska prawidłową odpowiedź o długości 100 znaków, ale uruchomienie zajmuje 120 sekund. Zadzwoń do tego programu . Na sprawdzisz ten program, ale jego uruchomienie trwa zbyt długo, więc musisz go odrzucić. Po sprawdzeniu wszystkich programów o długości 100 okazuje się, że żaden z nich nie udzielił właściwej odpowiedzi, więc wypróbowujesz programy o długości i wszystkie programy, które wypróbowałeś wcześniej . Więc spróbuj ponownie$i$$i$$P$$i=100$$101$ $P$, program, który (wiemy) da ci prawidłową odpowiedź, ale nadal trwa zbyt długo, więc musisz ją odrzucić. Kontynuujemy ten proces, aż dojdziemy do . Następnie wypróbowujemy wszystkie programy o długości , a kiedy dojdziemy do , pozwalamy mu działać wystarczająco długo, aby udzielić właściwej odpowiedzi. Potem przestajemy - znaleźliśmy algorytm, którego chcieliśmy. Iteracja, w której się znajdujemy to , ponieważ chociaż długość programu jest mniejsza (napisalibyśmy ), musieliśmy czekać, aż czas zajmie 120 sekund ( ). Więc oznacza po prostu maksimum długości programu$i=120$$\leq 120$$P$$i = 120$$P$$|P|=100$$s=120$$i=\mathrm{max}\{|P|,s\}$$P$a ilość czasu zajęło, aby uruchomić .$s$

Innym sposobem, aby na to spojrzeć, jest program który potrzebuje sekund na uzyskanie poprawnej odpowiedzi, musimy sprawdzić przynajmniejiteracji, a przynajmniej iteracji, zanim będziemy go znaleźć, bo jeślito nie sprawdziliśmy jeszcze tego programu, a jeśli , to nie pozwoliliśmy programowi działać wystarczająco długo.$P$$s$ $|P|$ $s$$i < |P|$$i < s$

Pamiętaj, że ta metoda wyszukiwania gwarantuje uzyskanie odpowiedzi tylko, jeśli taka istnieje; nie ma gwarancji znalezienia najkrótszej lub najszybszej odpowiedzi. Powód tego powinien być oczywisty, jeśli weźmiesz pod uwagę, że proces kończy się, gdy tylko znajdzie program, który da prawidłową odpowiedź.