Problem z zatrzymaniem maszyny Turinga

Input - Maszyna Turinga i ciąg wejściowy w.

Problem - Czy maszyna Turinga kończy obliczenia łańcucha ww skończonej liczbie kroków? Odpowiedź musi brzmieć tak lub nie.

Proof- Na początku założymy, że taka maszyna Turinga istnieje, aby rozwiązać ten problem, a potem pokażemy, że sama sobie zaprzecza. Nazwiemy tę maszynę Turinga jakoHalting machineco daje „tak” lub „nie” w ograniczonym czasie. Jeśli maszyna zatrzymująca zakończy pracę w skończonym czasie, na wyjściu pojawi się „tak”, w przeciwnym razie „nie”. Poniżej przedstawiono schemat blokowy maszyny zatrzymującej -

Teraz zaprojektujemy inverted halting machine (HM)’ jako -

• Gdyby H zwraca TAK, a następnie zapętla się na zawsze.

• Gdyby H zwraca NIE, a następnie zatrzymuje się.

Poniżej przedstawiono schemat blokowy „odwróconej maszyny zatrzymującej” -

Dalej maszyna (HM)₂ które samo wejście jest skonstruowane w następujący sposób -

• Jeśli (HM) ₂ zatrzyma się na wejściu, zapętlenie na zawsze.
• W przeciwnym razie zatrzymaj się.

Tutaj mamy sprzeczność. Stąd problem z zatrzymaniemundecidable.