Acceptproblemet for Turing-maskiner

Theorem 4.11

$A_{TM}$ er uafgørbart

Theorem 4.2.2

Et sprog $L$ er afgørbart hvis og kun hvis $L$ er genkendeligt og $\overline L$ er genkendeligt.

​ Altså: Et sprog er afgørbart præcis når både det og dets komplement er genkendeligt.

Corollary 4.23

$\overline {A_{TM}}$ er ikke genkendeligt

---

Last update: January 12, 2020