.pl .en .de .ru
Interdyscyplinarny blog badawczy pracowników Instytutu Językoznawstwa i Pracowni Systemów Informacyjnych UAM

Ilustrowany przewodnik po twierdzeniu Löba

Łukasz Borchmann

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.

03/31