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

Usunięte 39 bajtów ,  7 miesięcy temu
mer.
m (int.)
(mer.)
Dowód, że Entscheidungsproblem nie ma rozwiązania, stanowi wniosek w pracy Turinga wynikający z dwóch wcześniejszych lematów. Pierwszy lemat ma bliski związek z [[problem stopu|problemem stopu]], drugi z [[twierdzenie Rice’a|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" {{odn|Turing|1937|s=246}}. 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ę lub od pewnego momentu generuje wyłącznie symbole niezerowe nie jest "circle-free"){{odn|Turing|1937|s=233}}.
 
'''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 wyłączniekiedykolwiek danyokreś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 rozstrzygający czy Un(M) jest dowodliwe to M jest maszyną Turinga nie mogącą istnieć na mocy lematu 2{{odn|Turing|1937|s=259}}.