Dowód Turinga: Różnice pomiędzy wersjami

Dodane 10 bajtów ,  7 miesięcy temu
mer.
(mer.)
(mer.)
'''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){{odn|Turing|1937|s=248}}.
 
'''Lemat 3''' mówi, że odpowiednio dla każdej maszyny Turinga M można skonstruować formułę Un(M) i pokazać, że jeżeli istnieje ogólny, mechaniczny proces (maszyna Turinga) rozstrzygający czy Un(M) jest dowodliwe to Mistnieje jest maszynąmaszyna Turinga, która nie mogącąmoże istnieć na mocy lematu 2{{odn|Turing|1937|s=259}}.
 
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..."{{odn|Turing|1937|s=259}}.