Dowód Turinga: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
jęz. |
lin. |
||
Linia 13:
==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}}.
| |||