323
edycje
Dowód Turinga: Różnice pomiędzy wersjami
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
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}}.
| |||