Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 4 A18
Hi,
ich hänge bei der A18. Vermutlich macht man da Gegenbeweise mittels Halteproblem.
Aber ich denke mir, wenn meine Sprache entscheidbar ist, muss doch auch jede Teilmenge entscheidbar sein. Denn eine entscheidbare Sprache, ist doch
nur eine Menge aus Gödelnummern, die ich via Sytaxanalyse entscheide. Und eine Teilmenge daraus? Enthält nur Gödelnummern. Kann ich doch genauso entscheiden.
Was stimmt da nicht an meinem Ansatz?
Mfg greeny
Eine Sprache ist nicht notwendigerweise eine Ansammlung von Gödelnummern.
Jede Teilmenge aus Sigma* ist eine Sprache. Die Sprache, die alle Palindrome aus 0,1 enthält ist beispielsweise eine entscheidbare, nicht nur aus Gödelnummern bestehende Sprache.
Σ* ist entscheidbar. H⊂Σ* nicht.
1 Like
Womit du auch gleich die Lösung des derzeitigen Übungsblattes verraten hast ;).
Sorry, kannte die Aufgabe nicht, hab nur einen allgemeinen Fehler korrigiert 