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)