Informatiker Board | Theoretische Informatik | Sind die Fragen entscheidbar?

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

[quote][i]Original von marie m[/i]
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?[/quote]

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

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 $[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?