Informatiker Board | Theoretische Informatik | Sind die Fragen entscheidbar?

Informatiker Board » Themengebiete » Theoretische Informatik » Sind die Fragen entscheidbar?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Sind die Fragen entscheidbar?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Sind die Fragen entscheidbar?

Zitatantwort auf diesen Beitrag erstellen

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 $[latex]\phi[/latex]$ 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 [latex]2n+1[/latex]

im Definitionsbereich der Funktion $[latex]\phi[/latex]$ liegen, das $[latex]\phi(2n+1)[/latex]$ ist also für alle $[latex]n\in \mathbb{N}_0[/latex]$ definiert.

Wir betrachten die daher die Menge $[latex]M_1=\{i\in \mathbb{N}_0\mid \text{ Für alle } n\in \mathbb{N}_0 \text{ ist } \phi_i(2n+1) \text{ definiert }\}[/latex]$ .

Seien $[latex]i,j\in \mathbb{N}_0[/latex]$ mit $[latex]i\in M_1[/latex]$ und $[latex]\phi_i=\phi_j[/latex]$ . Wenn $[latex]i\in M_1[/latex]$ dann haben wir dass $[latex]\phi_i(2n+1)[/latex]$ definiert ist.

Da $[latex]\phi_i = \phi_j[/latex]$ folgt es dass $[latex]\phi_i (2n+1)= \phi_j (2n+1)[/latex]$ für alle $[latex]n\in \mathbb{N}_0[/latex]$ . Da $[latex]\phi_i(2n+1)[/latex]$ für alle $[latex]n\in \mathbb{N}_0[/latex]$ definiert ist, folgt es dass $[latex]\phi_j(2n+1)[/latex]$ auch für alle $[latex]n\in \mathbb{N}_0[/latex]$ definiert ist. Davon folgt es dass $[latex]j\in M_1[/latex]$ .

Das bedeutet dass [latex]M_1[/latex]

Funktionen respektiert.

Nach dem Satz von Rice ist [latex]M_1[/latex]

also genau dann entscheidbar, wenn $[latex]M_1 = \emptyset[/latex]$ oder $[latex]M_1 = \mathbb{N}_0[/latex]$ gilt.

Es gibt Indizes $[latex]i,j \in \mathbb{N}[/latex]$ mit $[latex]\phi_i(n) = 0[/latex]$ und $[latex]\phi_j(n) = n[/latex]$ für alle $[latex]n \in \mathbb{N}_0[/latex]$ , also gelten $[latex]i \in M_1[/latex]$ (und damit $[latex]M_1 \neq \emptyset[/latex]$ ) sowie $[latex]j \notin M_1[/latex]$ (und damit $[latex]M_1 \neq \mathbb{N}_0[/latex]$ ). Das heißt, [latex]M_1[/latex]

ist nach dem Satz von Rice nicht entscheidbar.

(b) Es ist entscheidbar, ob eine deterministische Turing-Maschine für irgendeine Eingabe kleiner oder gleich [latex]1000[/latex]

innerhalb der ersten [latex]1000[/latex]

Schritt hält.

Wir führen die Turing-Maschine nacheinander auf allen Wörtern $[latex]w \in \Sigma^{\star}[/latex]$ mit $[latex]w \leq 1000[/latex]$ für höchstens [latex]1000[/latex]

Schritte aus.

Wenn wir höchstens [latex]1000[/latex]

Schritte simuliert haben, halten wir und geben “ja” aus, ansonsten halten wir, sobald wir die Turing-Maschine auf allen Wörtern [latex]w[/latex]

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 $[latex]\phi[/latex]$ die Funktion die vom Algorithmus berechnet wird. Wir betrachten die Menge $[latex]M=\{i\in \mathbb{N}_0 \mid \text{ Für alle } n\in \mathbb{N}_0 \ \text{ ist } \phi_i(n) \ \text{ definiert }\}[/latex]$ , oder nicht?

Seien $[latex]i,j \in \mathbb{N}_0[/latex]$ mit $[latex]\phi_i = n[/latex]$ für eine natürliche Zahl $[latex]n\in \mathbb{N}[/latex]$ und $[latex]\phi_j\neq m\in \mathbb{N}[/latex]$ (da der Algorithmus für wenigstens eine Eingabe nicht hält).

Dann $[latex]i \in M[/latex]$ und $[latex]j \notin M[/latex]$ , also $[latex]M\neq \emptyset[/latex]$ 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?

14.07.2019 10:44

Nehmen Sie marie m in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Sind die Fragen entscheidbar?