Registermaschine/Entscheidbarkeit und Aufzählbarkeit/Fakt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Es sei eine Teilmenge der natürlichen Zahlen.

Dann ist genau dann -entscheidbar, wenn sowohl als auch das Komplement -aufzählbar ist.