5
Czy istnieje jakikolwiek konkretny związek między twierdzeniem o niekompletności Gödla, problemem zatrzymania a uniwersalnymi maszynami Turinga?
Zawsze myślałem niejasno, że odpowiedź na powyższe pytanie była twierdząca w następujący sposób. Twierdzenie Gödela o niekompletności i nierozstrzygalność problemu zatrzymania są zarówno negatywnymi wynikami rozstrzygalności, jak i ustalonymi na podstawie przekątnych argumentów (w latach 30. XX wieku), więc muszą być jakoś dwoma sposobami spojrzenia na te same sprawy. Pomyślałem, …