Jenseits von Chomsky
-
Jester schrieb:
Unsicherer schrieb:
Der echte Informatikker schrieb:
da es keine Turing-Maschine gibt die entscheiden kann ob ein Wort in dieser Sprache liegt (oder eben nicht darin liegt).
Das Halteproblem ist aber semi-entscheidbar und CH-0 Sprachen sind gerade die semi-entscheidbaren.
Dann eben doch, wie schon oben vorgeschlagen, das Komplement. Imo ist damit die Frage geklärt, oder?
Klar, hab es ja selbst vorgeschlagen. Allerdings ändert das nichts daran, dass die zitierte Behauptung falsch ist.
-
@Der echte Informatikker: Sorry, deine ersten Antworten waren einfach zu kurz und unkonkret.
Unsicher schrieb:
Klar, hab es ja selbst vorgeschlagen.
Klar, habe wir alle.
PS: Auch habe ich mir Logikbuch gekauft, um herauszufinden, ob die Halteproblemmenge eine Menge im Sinne ZFC ist. Kann ja meine Erkenntnisse posten ... so in einem halben Jahr.
-
knivil schrieb:
PS: Auch habe ich mir Logikbuch gekauft, um herauszufinden, ob die Halteproblemmenge eine Menge im Sinne ZFC ist. Kann ja meine Erkenntnisse posten ... so in einem halben Jahr.
Stichwort Aussonderungsaxiom.