Dowód Turinga: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m int. |
mer. |
||
Linia 15:
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ę
'''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
'''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}}.
| |||