zatrzymaniu się wywołania test(test) oraz o rozstrzygalności problemu stopu przez procedurę stop;
Powyższy dowód nie wprost zaprowadził nas do sprzeczności z początkowymi założeniami, z czego wynika, iż nie istnieje taki uniwersalny algorytm, który rozstrzyga problem stopu dla dowolnego algorytmu.
Zobacz też twierdzenie Gödla pracowity bóbr
Przypisy
Kategoria:Teoria obliczeń Kategoria:Algorytmika