Sind Teilmengen von N immer abzählbar?
-
Sind Teilmengen von N immer abzählbar?
-
Ja.
-
Man kann jede Turing-Maschine als natürliche Zahl kodieren.
Betrachte die Teilmenge der natürlichen Zahlen, die Kodierung einer Turing-Maschine sind, die bei leerer Eingabe anhält. Diese Menge ist nicht entscheidbar. Ist sie dennoch abzählbar?
-
Ja.
Bau dir doch einfach ne Bijektion zwischen |N und einer beliebigen Teilmenge (mit unendlich vielen Elementen) von |N. Turing-Maschinen verwirren nur...
-
Turing-Maschinen haben hier nichts verloren, du fragst nach Abzählbarkeit, nicht nach (rekursiver) Aufzählbarkeit.