Geschrieben von marie m am 14.07.2019 um 10:44:
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
die Funktion die von ein Algorithmus berechnet wird.
Da der Algorithmus bei jeder Eingabe ungerader Länge hält haben wir dass die Elemente der Form
im Definitionsbereich der Funktion
liegen, das
ist also für alle
definiert.
Wir betrachten die daher die Menge
.
Seien
mit
und
. Wenn
dann haben wir dass
definiert ist.
Da
folgt es dass
für alle
. Da
für alle
definiert ist, folgt es dass
auch für alle
definiert ist. Davon folgt es dass
.
Das bedeutet dass
Funktionen respektiert.
Nach dem Satz von Rice ist
also genau dann entscheidbar, wenn
oder
gilt.
Es gibt Indizes
mit
und
für alle
, also gelten
(und damit
) sowie
(und damit
). Das heißt,
ist nach dem Satz von Rice nicht entscheidbar.
(b) Es ist entscheidbar, ob eine deterministische Turing-Maschine für irgendeine Eingabe kleiner oder gleich
innerhalb der ersten
Schritt hält.
Wir führen die Turing-Maschine nacheinander auf allen Wörtern
mit
für höchstens
Schritte aus.
Wenn wir höchstens
Schritte simuliert haben, halten wir und geben “ja” aus, ansonsten halten wir, sobald wir die Turing-Maschine auf allen Wörtern
simuliert haben, und geben “nein” aus.
(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
die Funktion die vom Algorithmus berechnet wird. Wir betrachten die Menge
, oder nicht?
Seien
mit
für eine natürliche Zahl
und
(da der Algorithmus für wenigstens eine Eingabe nicht hält).
Dann
und
, also
und [latex]M\neq \mathbb{N}_0[l/atex], und jetzt kann man den Satz von Rice anwenden.
Ist alles richtig? Könnte ich etwas verbessern?