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

Rozmiar się nie zmienił ,  7 miesięcy temu
jęz.
(lin.)
(jęz.)
'''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{{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}}.
 
== Zobacz też ==