.pl .en .de .ru
Interdyscyplinarny blog badawczy pracowników Zakładu Infolingwistyki i Zakładu Przetwarzania Języka Naturalnego UAM

Ilustrowany przewodnik po twierdzeniu Löba

Łukasz Borchmann
03/31

Twierdzenia Löba stanowi, że jeśli maszyna löbowska (np. arytmetyka Peano) może dowieść, że jeśli P jest możliwe do dowiedzenia, to P jest prawdą, to P jest w jej ramach możliwe do dowiedzenia. Tak więc, na przykład, dowód na to, że jeśli w arytmetyce Peano da się dowieść hipotezy Goldbacha, to jest ona prawdziwa byłby dowodem na to, że hipoteza Goldbacha jest prawdziwa.

Twierdzenia Löba przywołuje się niekiedy w tekstach dotyczących silnej sztucznej inteligencji, ponieważ ilustruje podstawowy rodzaj samoodniesienia, które ma miejsce gdy algorytm rozważa swoje wyjście jako część świata i ma być w związku z tym istotne przy pracy z samomodyfikującymi się agentami (zob. np. An Introduction to Löb’s Theorem in MIRI Research).

Poniżej jego komiksowe wyjaśnienie opublikowane przez Eliezera Yudkowskiego, jako The Cartoon Guide to Löb’s Theorem. Od wersji oryginalnej różni się 9. krokiem, w którym, jak mniemam, autorowi wkradł się błąd i napisał (1, MP) zamiast (8, 1, MP).

Tagi