Maszyna Gödla

Maszyna Gödla to hipotetyczny samodoskonalący się program komputerowy , który rozwiązuje problemy w optymalny sposób. Wykorzystuje rekurencyjny protokół samodoskonalenia, w którym przepisuje własny kod, gdy może udowodnić, że nowy kod zapewnia lepszą strategię. Maszyna została wynaleziona przez Jürgena Schmidhubera (po raz pierwszy zaproponowana w 2003 r.), Ale nosi imię Kurta Gödla , który zainspirował teorie matematyczne.

Maszyna Gödla jest często omawiana w przypadku zagadnień związanych z metauczeniem , znanym również jako „uczenie się, jak się uczyć”. Aplikacje obejmują automatyzację decyzji projektowych podejmowanych przez człowieka i transfer wiedzy między wieloma powiązanymi zadaniami i mogą prowadzić do projektowania solidniejszych i ogólnych architektur uczenia się. Chociaż teoretycznie jest to możliwe, nie stworzono pełnej implementacji.

Maszyna Gödla jest często porównywana z AIXI Marcusa Huttera , inną formalną specyfikacją ogólnej sztucznej inteligencji . Schmidhuber zwraca uwagę, że maszyna Gödla mogłaby zacząć od zaimplementowania AIXItl jako swojego początkowego podprogramu i modyfikować się samodzielnie po znalezieniu dowodu, że inny algorytm dla jej kodu wyszukiwania będzie lepszy.

Ograniczenia

Tradycyjne problemy rozwiązywane przez komputer wymagają tylko jednego wejścia i dają pewien wynik. Komputery tego rodzaju miały swój początkowy algorytm na stałe. Nie uwzględnia to dynamicznego środowiska naturalnego, dlatego maszyna Gödla była celem do pokonania.

Maszyna Gödla ma jednak swoje własne ograniczenia. Zgodnie z pierwszym twierdzeniem Gödla o niezupełności każdy system formalny obejmujący arytmetykę jest albo wadliwy, albo dopuszcza twierdzenia, których nie można udowodnić w systemie. Dlatego nawet maszyna Gödla z nieograniczonymi zasobami obliczeniowymi musi ignorować te samodoskonalenia, których skuteczności nie może udowodnić.

Interesujące zmienne

Istnieją trzy zmienne, które są szczególnie przydatne w czasie wykonywania maszyny Gödla.

• $displaystyle {\ text {time}}}$ pewnym momencie zmienna $\$ będzie miała binarny odpowiednik ${\ displaystyle t}$ . Wartość ta jest stale zwiększana przez cały czas pracy maszyny.

• Wszelkie dane wejściowe przeznaczone dla maszyny Gödla ze środowiska naturalnego są przechowywane w zmiennej ${\ displaystyle x}$ . Jest prawdopodobne, że $wartości$ dla różnych wartości zmiennej ${\ Displaystyle {\ tekst {czas}}}$ .

• $Dane$ maszyny Gödla są przechowywane w zmiennej $,$ wyjściowym bitów $w$ pewnym

W dowolnym momencie , gdzie $displaystyle$ maksymalizacja przyszłego sukcesu lub $t$ Typowa funkcja użyteczności jest zgodna ze wzorem ${\ Displaystyle u (s, \ operatorname {Env}): S \ razy E \ rightarrow \ mathbb {R}}$ :

${\ Displaystyle u (s, \ operatorname {Env}) = E _ {\ mu} {\ Bigg [}\sum _{\tau ={\text{czas}}}^{T}r(\tau )\mid s,\mathrm {Środowisko} {\Bigg ]}}$

gdzie ${\ Displaystyle r (t)}$ jest wartością wejściową nagrody (zakodowaną w $}$ czasie $\ displaystyle t$ , $mu} [\ cdot \ mid \ cdot ]}$$M}$ oznacza warunkowy operator oczekiwań w odniesieniu do jakiejś prawdopodobnie nieznanej dystrybucji ze zbioru $displaystyle$ możliwych rozkładów ( $odzwierciedla$ wszystko, co wiadomo o prawdopodobnie probabilistycznych reakcjach środowiska), a wspomniany powyżej ${\ Displaystyle {\ tekst {czas}} = \ operatorname$ jest funkcją stanu $jednoznacznie$ identyfikuje bieżący cykl. Pamiętaj, że bierzemy pod uwagę możliwość wydłużenia oczekiwanej żywotności poprzez odpowiednie działania.

Instrukcje stosowane przez techniki dowodowe

Charakter sześciu poniższych instrukcji modyfikujących dowód uniemożliwia wstawienie niepoprawnego twierdzenia do dowodu, co trywializuje weryfikację dowodu.

get-aksjomat( n )

Dołącza n -ty aksjomat jako twierdzenie do bieżącego ciągu twierdzeń. Poniżej znajduje się początkowy schemat aksjomatów:

• Aksjomaty sprzętowe formalnie określają, w jaki sposób komponenty maszyny mogą zmieniać się z jednego cyklu do drugiego.
• Aksjomaty nagrody określają koszt obliczeniowy instrukcji sprzętowych i fizyczny koszt działań wyjściowych. Powiązane aksjomaty definiują również czas życia maszyny Gödla jako skalarne reprezentujące wszystkie nagrody/koszty.
• Aksjomaty środowiska ograniczają sposób, w jaki nowe dane wejściowe x są wytwarzane ze środowiska, w oparciu o poprzednie sekwencje danych wejściowych y .
• Aksjomaty niepewności/manipulowanie strunami Aksjomaty to standardowe aksjomaty dla arytmetyki, rachunku różniczkowego, teorii prawdopodobieństwa i manipulacji strunami, które pozwalają na konstruowanie dowodów związanych z przyszłymi wartościami zmiennych w maszynie Gödla.
• Aksjomaty stanu początkowego zawierają informacje o tym, jak zrekonstruować część lub całość stanu początkowego.
• Aksjomaty użyteczności opisują ogólny cel w postaci funkcji użyteczności u .

zastosuj-regułę( k , m , n )

Bierze indeks k reguły wnioskowania (np. Modus tollens , Modus ponens ) i próbuje zastosować go do dwóch wcześniej udowodnionych twierdzeń m i n . Otrzymane twierdzenie jest następnie dodawane do dowodu.

twierdzenie o usunięciu ( m )

Usuwa twierdzenie zapisane pod indeksem m w bieżącym dowodzie. Pomaga to złagodzić ograniczenia przechowywania spowodowane przez zbędne i niepotrzebne twierdzenia. Do usuniętych twierdzeń nie można już odwoływać się przez powyższą zastosowania reguły .

set-switchprog( m , n )

Zastępuje switchprog S ^pm _{:n , pod warunkiem} , ^p że jest to niepusty podłańcuch S .

sprawdzać()

Sprawdza, czy cel wyszukiwania dowodu został osiągnięty. Docelowe twierdzenie mówi, że biorąc pod uwagę obecną aksjomatyzowaną funkcję użyteczności u (pozycja 1f), użyteczność przełączenia z p na bieżący program przełączenia byłaby większa niż użyteczność kontynuacji wykonywania p (co oznaczałoby dalsze poszukiwanie alternatywnych programów przełączenia).

Twierdzenie o stanie2( m , n )

Przyjmuje dwa argumenty, m i n , i próbuje przekonwertować zawartość S _m:n na twierdzenie.

Przykładowe aplikacje

Ograniczona w czasie optymalizacja NP-trudna

Początkowym wejściem do maszyny Gödla jest reprezentacja połączonego grafu z dużą liczbą węzłów połączonych krawędziami o różnych długościach. W zadanym czasie T powinien znaleźć ścieżkę cykliczną łączącą wszystkie węzły. Jedyna nagroda o wartości rzeczywistej pojawi się w czasie T . Jest równy 1 podzielonemu przez długość najlepszej znalezionej do tej pory ścieżki (0, jeśli nie znaleziono żadnej). Nie ma innych wejść. Produktem ubocznym maksymalizacji oczekiwanej nagrody jest znalezienie najkrótszej możliwej do znalezienia ścieżki w ograniczonym czasie, biorąc pod uwagę początkowe odchylenie.

Szybkie dowodzenie twierdzeń

Jak najszybciej udowodnij lub obal, że wszystkie liczby całkowite parzyste > 2 są sumą dwóch liczb pierwszych ( hipoteza Goldbacha ). Nagroda wynosi 1/ t , gdzie t jest czasem potrzebnym do sporządzenia i zweryfikowania pierwszego takiego dowodu.

Maksymalizacja oczekiwanej nagrody przy ograniczonych zasobach

Kognitywny robot , który potrzebuje co najmniej 1 litr benzyny na godzinę, wchodzi w interakcję z częściowo nieznanym środowiskiem, próbując znaleźć ukryte, ograniczone magazyny benzyny, aby od czasu do czasu zatankować swój zbiornik. Jest nagradzany proporcjonalnie do swojego życia i umiera po co najwyżej 100 latach lub gdy tylko jego zbiornik się opróżni lub spadnie z klifu i tak dalej. probabilistyczny _ reakcje środowiskowe są początkowo nieznane, ale zakłada się, że pochodzą z aksjomatyzowanej prędkości wcześniejszej, zgodnie z którą trudne do obliczenia reakcje środowiskowe są mało prawdopodobne. Pozwala to na obliczalną strategię dokonywania prawie optymalnych prognoz. Jednym z produktów ubocznych maksymalizacji oczekiwanej nagrody jest maksymalizacja oczekiwanego czasu życia.

Zobacz też

• Twierdzenia Gödla o niezupełności

Linki zewnętrzne

• Strona główna Gödel Machine