Sind die Fragen entscheidbar? |
14.07.2019, 10:44 | Auf diesen Beitrag antworten » |
marie m | Sind die Fragen entscheidbar? Hallo, ich gucke folgende Aufgabe: Sind die folgenden Fragen entscheidbar? Geben Sie einen entsprechenden Algorithmus an oder zeigen Sie mit Hilfe des Satzes von Rice, daß das Problem unentscheidbar ist. (a) Hält ein beliebiger Algorithmus bei jeder Eingabe ungerader Länge? (b) Hält eine beliebige Turingmaschine auf allen Eingaben kleiner oder gleich 1000 innerhalb der ersten 1000 Schritte? (c) Gibt ein beliebiger Algorithmus bei geeigneter Eingabe eine Zahl aus, die als String interpretiert ein Palindrom ist? (d) Liefert ein beliebiger Algorithmus, der für wenigstens eine Eingabe nicht hält, jede natürliche Zahl als Ausgabewert? Ich habe folgendes gemacht: (a) Sei Da der Algorithmus bei jeder Eingabe ungerader Länge hält haben wir dass die Elemente der Form Wir betrachten die daher die Menge Seien Da Das bedeutet dass Nach dem Satz von Rice ist Es gibt Indizes (b) Es ist entscheidbar, ob eine deterministische Turing-Maschine für irgendeine Eingabe kleiner oder gleich Wir führen die Turing-Maschine nacheinander auf allen Wörtern Wenn wir höchstens (c) Um den Satz von Rice anzuwenden muss man eine Funktion finden die eine palindrome Ausgabe hat und eine Funktion die keine palindrome Ausgabe hat, um eine nicht-triviale Eigenschaft zu bekommen? (d) Sei Seien Dann Ist alles richtig? Könnte ich etwas verbessern? |
|
|