“Entscheidbar” und “semientscheidbar”

Entscheidbare und semientscheidbare Sprachen

Für eine entscheidbare Sprache kann eine Turingmaschine in endlich vielen Schritten die Frage, ob ein Wort Element der Sprache ist, mit JA oder NEIN beantworten. Insbesondere hällt die Turingmaschine für eine entscheidbare Sprache also an, wenn das Wort nicht aus der Sprache kommen kann.

Für eine semientscheidbare Sprache kann eine Turingmaschine auch herausfinden, ob das Wort Element der Sprache ist. Jedoch hällt die Turingmaschine im Falle der Antwort NEIN nie an – weshalb man im Prinzip unendlich lange auf die Antwort NEIN warten müsste.

Bezüglich der Komplexität gilt also insbesondere: Entschiedbare Sprachen sind auch semientscheidbar – bilden also eine Teilmenge der semientscheidbaren Sprachen.