Ist ein Wort in der Sprache?
→ Ist ein Entscheidungsproblem
→ Heißt Wortproblem
Kann ein Wort von der Sprache erkannt, rekusive aufgezählt werden?
→ Ist das Halteproblem
→ Dieses Probem ist semi-entscheidbar
⇒ Das Wortproblem kann gelöst werden das Halteproblem für und gelöst werden kann. (semi-entscheidbar und co-semi-entscheidbar)