Sprache semientscheidbar |
12.06.2017, 19:41 | Rina4649620523ß45 | Auf diesen Beitrag antworten » |
Sprache semientscheidbar hallo , ich soll entscheiden ob die sprache "<M>: M hält auf jeder Eingabe w2 entweder nach frühestens w^2 vielen Schritten oder gar nicht" rekursiv aufzahlbar ist und ob das komplement auch rek aufzählbar ist . Meine Ideen: Meine Überlegung war das diese nicht rekursiv aufzählbar ist weil man ja eine universelle TM konstuieren kann aber dieses nach frühstens w^2 vielen Schritten quasi alles zerstort weil ein wort ja akzeptierne kann aber halt nach w^2 vielen Schritten was die TM dann nicht erkennt Liege ich damit schonmal richtig? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|