Pierwszy lemat ma bliski związek z problemem stopu, drugi z twierdzeniem Rice’a.
Lemat 1 mówi, że nie istnieje maszyna Turinga, zdolna rozstrzygnąć w skończonej liczbie kroków czy dowolna maszyna Turinga jest "circle-free". Dana maszyna jest "circle-free" jeżeli nie istnieje górne, skończone ograniczenie na liczbę symboli zerowych lub niezerowych, które generuje maszyna (np. maszyna, która kończy pracę nie jest "circle-free").
Lemat 2 mówi, że nie istnieje maszyna Turinga, która jest w stanie rozstrzygnąć w skończonej liczbie kroków czy dana maszyna Turinga generuje kiedykolwiek określony symbol (np. symbol zerowy). Jeżeliby tak było, prowadziłoby to do sprzeczności z lematem 1.
Lemat 3 mówi, że odpowiednio dla każdej maszyny Turinga M można skonstruować formułę Un(M) i nie istnieje ogólny, mechaniczny proces (maszyna Turinga) rozstrzygający czy Un(M) jest dowodliwe. Jeżeliby tak było, prowadziłoby to do sprzeczności z lematem 2.
Turing napisał: "Warto zaznaczyć, że to ... różni się od dobrze znanych wyników Gödla. Gödel pokazał, że (w formalizmie Principia Mathematica) istnieją twierdzenia T takie, że ani T ani ~T nie jest dowodliwe. Ja ... pokazuję, że nie istnieje ogólna (mechaniczna) metoda, która pozwala sprawdzić czy dana formuła T jest dowodliwa...".
Zobacz też Twierdzenie Gödla
Przypisy
Bibliografia
Kategoria:Teoria obliczeń Kategoria:Logika matematyczna