Jakie jest jasne wyjaśnienie uniwersalnego wyszukiwania?

13

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 ).

ilościowo
źródło

Odpowiedzi:

15

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.xxx

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 jaiiii

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.Psi=max{|P|,s}sP

Pål GD
źródło
3

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 ponownieiiPi=100101 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 programui=120120Pi=120P|P|=100s=120i=max{|P|,s}Pa 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.Ps |P| si<|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ź.

Tom Potts
źródło