רדוקציות

ATM ≤m HALTTM

רדוקציית מיפוי כריעה המוכיחה ש־HALTTM אינה כריעה, בהנחה ש־ATM אינה כריעה. הבנייה עוטפת את M למכונה חדשה M′ שהופכת "קבלה" ל"עצירה" ו"דחייה" ל"לולאה אינסופית".

שתי הבעיות

ATM
מופע: מכונת טיורינג M ומחרוזת w.
שאלה: האם M מקבלת את w?
HALTTM
מופע: מכונת טיורינג M′ ומחרוזת w.
שאלה: האם M′ עוצרת על w (בכל מצב — קבלה או דחייה)?

הבנייה

בהינתן מופע ATM ⟨M, w⟩, בנו מופע HALTTM ⟨M′, w⟩ כאשר M′ היא מכונת הטיורינג הבאה:

M' on input x:
  1. Simulate M on x.
  2. If M accepts x, halt.
  3. If M rejects x, enter an infinite loop.

תיאור M′ ניתן לחישוב מתיאור M, כך שההעתקה ⟨M, w⟩ ↦ ⟨M′, w⟩ היא פונקציה כריעה. (לא נדרש חסם פולינומיאלי — אנו זקוקים רק לכך שהפונקציה תהיה כריעה.)

המחשה

שלב 1 / 4מופע ATM
ATM instance
⟨M, w⟩
→
HALTTM instance
⟨M′, w⟩
בניית M′
M' on input x:
  1. Simulate M on x.
  2. If M accepts x, halt.
  3. If M rejects x, enter an infinite loop.
M on wM′ on w⟨M, w⟩ ∈ ATM⟨M′, w⟩ ∈ HALTTM
מקבלתעוצרתכןכן
דוחהלולאהלאלא
לולאהלולאהלאלא
⟨M, w⟩ ∈ ATM  ⟺  ⟨M′, w⟩ ∈ HALTTM

קלט ⟨M, w⟩: מכונת טיורינג M ומחרוזת w. שאלת ATM היא האם M מקבלת את w.

נכונות

(⇒) אם M מקבלת את w, אז לפי הבנייה M′ עוצרת על w. לכן ⟨M′, w⟩ ∈ HALTTM.
(⇐) אם M אינה מקבלת את w, אז M או דוחה את w או נכנסת ללולאה על w. בשני המקרים הבנייה גורמת ל־M′ להיכנס ללולאה על w, כך ש־⟨M′, w⟩ ∉ HALTTM.
לפיכך ⟨M, w⟩ ∈ ATM אם ורק אם ⟨M′, w⟩ ∈ HALTTM. מאחר ש־ATM אינה כריעה, HALTTM אינה כריעה. ∎