Registermaschine/Entscheidbarkeit und Aufzählbarkeit/Fakt

Es sei ${}T\subseteq \mathbb {N}$ eine Teilmenge der natürlichen Zahlen.

Dann ist ${}T$ genau dann ${}R$ -entscheidbar, wenn sowohl ${}T$ als auch das Komplement ${}\mathbb {N} \setminus T$ ${}R$ -aufzählbar ist.

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.