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

Dodane 4 bajty ,  7 miesięcy temu
lin.
(jęz.)
(lin.)
==Dowód==
 
Dowód, że [[Entscheidungsproblem]] nie ma rozwiązania (lemat 3), 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ę nie jest "circle-free"){{odn|Turing|1937|s=233}}.