Halteproblem/vereinfacht/0 Ein < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 05:40 Mi 22.05.2013 | | Autor: | Lu- |
| Aufgabe | Sei H' := [mm] \{ n : U(n,0) haelt \}, [/mm] d.h. die Menge derjenigen source codes n die auf Input 0 halten. Zeige H' ist nicht rekursiv.
Hinweis: Ansonsten können wir H:= [mm] \{ n : U(n,n) haelt \} [/mm] (habe ich schon gezeigt, dass die Menge nicht rekursiv ist) entscheiden: Gegeben n. Um zu sehen ob n in H transformiere den source code n zu einem neuenen source-code g(n): Dieses neue Programm g(n) überschreibt die input-variable mit n und danach wird einfach das alte Programm n ausgeführt. Argumentiere mit Curch-Turing-These(nicht formal) dass g total und rekursiv ist |
Defnition: Menge H' nicht rekursiv <=> charakteristische Funktion [mm] \chi_{H'} [/mm] nicht rekursiv
[mm] \chi_{H'} [/mm] : n -> [mm] \begin{cases} 1, & \mbox{für } n\in H' \mbox{ d.h.} U(n,0) \mbox{ haelt} \mbox{bzw. gleichbedeutend} U(n,0) \mbox{ ist definiert} \\ 0, & \mbox{sonst } \end{cases}
[/mm]
Ang [mm] \chi_{H'} [/mm] rekursiv also mittels Goto-Programm M' berechenbar (Vo: Funktion rekursiv <=> Goto-Programm für die Funktion existiert)
Versuch ist nun:
Eingabe für [mm] \chi_{H} [/mm] -> Funktion g anwenden -> Eingabe für [mm] \chi_{H'}-> [/mm] Programm M
gesucht g: [mm] \chi_H [/mm] (i)= [mm] \chi_{H'} [/mm] (g(i)) und g total & Rekursiv
D.h.: n [mm] \in [/mm] H <=> g (n) [mm] \in [/mm] H'
Ich versuchte sowas wie g: n -> U(n,0) aber das ging schief.
U(n,0)... simuliere [mm] U_n [/mm] mit Eingabe 0
Auch eine Idee war die Identität- Aber wieso sollte wenn [mm] U_n [/mm] auf Eingabe n auch [mm] U_n [/mm] auf Eingabe 0 halten??
EDIT:
Jedem Goto-Programm E wird ein sourcecode [mm] P_E \in \IN [/mm] zugeordnet. Ein Programm U dass auf [mm] Input(P_E [/mm] , n) den output liefert, den dass Programm E auf input n liefern würde ist ein universelles Progamm)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:08 Mi 22.05.2013 | | Autor: | tobit09 |
Hallo Lu-,
zwar fühle ich mich nicht kompetent genug, die Aufgabe zu lösen. Aber zur Frage nach einem geeigneten g: Befolge den Hinweis!
[mm] $g(n):=P_{E(n)}$
[/mm]
mit
$E(n):=$ ein goto-Programm, das zunächst die Eingabe mit $n$ überschreibt und dann [mm] $U_n$ [/mm] ausführt.
(Ich hoffe, ich habe eure Notationen richtig interpretiert und verwendet.)
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 06:14 Mi 22.05.2013 | | Autor: | Lu- |
Hallo,
da taucht bei mir gleich die Frage auf (die ich mir auch gestellt habe, als ich den Hinweis gelesen habe)
> $ E(n):= $ ein goto-Programm, das zunächst die Eingabe mit $ n $ überschreibt und dann $ [mm] U_n [/mm] $ ausführt.
Welche Eingabe/Was ist die Eingabe? Ich dachte vorher n also das argument von g ist die Eingabe. Aber n mit n überschreiben gibt doch keinen Sinn?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:19 Mi 22.05.2013 | | Autor: | tobit09 |
> da taucht bei mir gleich die Frage auf (die ich mir auch
> gestellt habe, als ich den Hinweis gelesen habe)
> > [mm]E(n):=[/mm] ein goto-Programm, das zunächst die Eingabe mit
> [mm]n[/mm] überschreibt und dann [mm]U_n[/mm] ausführt.
> Welche Eingabe/Was ist die Eingabe? Ich dachte vorher n
> also das argument von g ist die Eingabe. Aber n mit n
> überschreiben gibt doch keinen Sinn?
Vergiss für einen Moment die Abbildung $g$. Wir sind jetzt nur bei der Definition von $E(n)$.
Jedes goto-Programm verarbeitet ja eine Eingabe (input-variable). Prinzipiell kann jedes goto-Programm mit jeder Eingabe gestartet werden.
$E(n)$ ist nun ein goto-Programm, dass die Eingabe förmlich ignoriert: Egal, mit welcher Eingabe man es startet: Es überschreibt sie sofort mit $n$.
Dann führt $E(n)$ das Programm [mm] $U_n$ [/mm] aus.
Also egal, mit welcher Eingabe man $E(n)$ startet: $E(n)$ verhält sich bezüglich Halteverhaltens (und im Falle des Haltens auch bezüglich der Ausgabe) genauso, wie sich [mm] $U_n$ [/mm] bei Eingabe $n$ verhalten würde.
Insbesondere hält $E(n)$ bei Eingabe $0$ genau dann, wenn [mm] $U_n$ [/mm] bei Eingabe $n$ hält.
Also:
[mm] $n\in [/mm] H$
[mm] $\iff [/mm] U(n,n)$ hält
[mm] $\iff U_n$ [/mm] hält bei Eingabe $n$
[mm] $\iff [/mm] E(n)$ hält bei Eingabe $0$
[mm] $\iff U_{P_{E(n)}}$ [/mm] hält bei Eingabe $0$
[mm] $\iff U(\underbrace{P_{E(n)}}_{=g(n)},0)$ [/mm] hält
[mm] $\iff g(n)\in [/mm] H'$.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:05 Mi 22.05.2013 | | Autor: | Lu- |
| Aufgabe | Def.: Wir sagen A ist may-one-reducible zu B, in Zeiichen : A [mm] \le_{m} [/mm] B wenn es eine totale rekursive Funktion g gibt sodaß A= [mm] g^{-1} [/mm] (B)
Setzte A=_{m} B wenn A [mm] \le_{m} [/mm] B und B [mm] \le_{m} [/mm] A
Wir haben zuvor gezeigt, dass H [mm] \le_{m} [/mm] H' . Setzte [mm] H^{\*} [/mm] := [mm] \{(n,m) : U(n,m) haelt\}. [/mm] Zeihe H=_{m} H' =_{m} H*
Hinweis: Es ist einfach zu sehen, dass H* "stärker" als H' ist, umzusehen dass H* [mm] \le_{m} [/mm] H verwende im wesentlichen dasselbe Argument wie für H [mm] \le_{m} [/mm] H' |
Vielen dank!!
Warum sollte aber nun g total sein? Also überall definiert sein? Die Church-Thuring-These sagt mir ja nur, dass ich für E einen maschinellen algorithmus habe und deshalb implementieren kann in irgendeiner Computer-Sprache und somit ist es goto-Berechenbar, woraus rekursiv folgt.
Zu nächsten Aufgabe:
Ich glaub im Hinweis ist ein Druckfehler, und man solle zeigen: H* [mm] \le_{m} [/mm] H' und nicht H* [mm] \le_{m} [/mm] H)
H [mm] \le_{m} H^{\*}
[/mm]
Funktion f total & rekursiv mit
n [mm] \in [/mm] H <=> f(n) [mm] \in H^{\*}
[/mm]
f(n):= (n,n)
n [mm] \in [/mm] H
[mm] <=>U_n [/mm] hält bei Eingabe n
<=> (n,n) =f(n) [mm] \in H^{\*}
[/mm]
[mm] H^{\*} \ge [/mm] H'
Funktion s total & rekursiv mit
n [mm] \in [/mm] H' <=> s(n) [mm] \in H^{\*}
[/mm]
s(n):=(n,0)
n [mm] \in [/mm] H '
<=> [mm] U_n [/mm] hält bei Eingabe 0
<=> s(n)=(n,0) [mm] \in H^{\*}
[/mm]
[mm] H^{\*} \le [/mm] H'
Funktion [mm] \phi [/mm] total & rekursiv mit
(n,m) [mm] \in H^{\*} [/mm] <=> [mm] \phi(n,m) \in [/mm] H'
E: goto programm, dass Eingabe immer mit m überschreibt und [mm] U_n [/mm] angesetzt auf m ausführt
[mm] \phi [/mm] (n,m)= [mm] P_E
[/mm]
(n,m ) [mm] \in H^{\*} [/mm]
<=>U(n,m) hält
[mm] <=>U_n [/mm] angesetzt auf m hält
[mm] \overbrace{<=>}^{?} [/mm] E hält bei Eingabe 0
<=> [mm] U_{P_E} [/mm] hält bei EIngabe 0
<=> [mm] \phi(n,m) \in [/mm] H'
bleibt zuzeigen:
H [mm] \ge_{m} [/mm] H'
Stecke ich ..;( Oder soll ich was anderes zeigen( wie [mm] H^{\*} \ge_{m} [/mm] H )? Und mit der transitivität arbeiten? Ist das einfacher?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:22 Do 23.05.2013 | | Autor: | tobit09 |
> Warum sollte aber nun g total sein? Also überall definiert
> sein? Die Church-Thuring-These sagt mir ja nur, dass ich
> für E einen maschinellen algorithmus habe und deshalb
> implementieren kann in irgendeiner Computer-Sprache und
> somit ist es goto-Berechenbar, woraus rekursiv folgt.
Wir haben $g$ ja auf ganz [mm] $\IN$ [/mm] definiert, indem wir [mm] $g(n)=\ldots$ [/mm] für alle [mm] $n\in\IN$ [/mm] gesetzt haben. Also ist klar, dass $g$ total ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:35 Fr 24.05.2013 | | Autor: | tobit09 |
> Zu nächsten Aufgabe:
> Ich glaub im Hinweis ist ein Druckfehler, und man solle
> zeigen: H* [mm]\le_{m}[/mm] H' und nicht H* [mm]\le_{m}[/mm] H)
Nein, dass ist kein Druckfehler. Die Idee aus dem Hinweis ist,
[mm] $H\le_m H'\le_m H^\*\le_m [/mm] H$
zu zeigen. Mit der Transitivität von [mm] $\le_m$ [/mm] folgt dann die Behauptung.
> Oder soll ich was anderes zeigen( wie
> [mm]H^{\*} \ge_{m}[/mm] H )? Und mit der transitivität arbeiten?
> Ist das einfacher?
Der Vorschlag aus dem Hinweis hat den Vorteil, dass nur noch zwei [mm] $\le_m$-Beziehungen [/mm] zu zeigen sind, während du noch vier [mm] $\le_m$-Beziehungen [/mm] durchgehst (von denen [mm] $H^{\*} \ge [/mm] H'$ überflüssig zu zeigen ist).
Die Schwierigkeit, die einzelnen [mm] $\le_m$-Beziehungen [/mm] zu zeigen, unterscheiden sich aus meiner Sicht nicht, abgesehen von [mm] $H'\le_m H^\*$ [/mm] und [mm] $H\le_m H^\*$, [/mm] die einfacher sind als die übrigen.
> H [mm]\le_{m} H^{\*}[/mm]
> Funktion f total & rekursiv mit
> n [mm]\in[/mm] H <=> f(n) [mm]\in H^{\*}[/mm]
> f(n):= (n,n)
> n [mm]\in[/mm] H
> [mm]<=>U_n[/mm] hält bei Eingabe n
> <=> (n,n) =f(n) [mm]\in H^{\*}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> [mm]H^{\*} \ge[/mm] H'
> Funktion s total & rekursiv mit
> n [mm]\in[/mm] H' <=> s(n) [mm]\in H^{\*}[/mm]
> s(n):=(n,0)
> n [mm]\in[/mm] H '
> <=> [mm]U_n[/mm] hält bei Eingabe 0
> <=> s(n)=(n,0) [mm]\in H^{\*}[/mm]
> [mm]H^{\*} \le[/mm] H'
> Funktion [mm]\phi[/mm] total & rekursiv mit
> (n,m) [mm]\in H^{\*}[/mm] <=> [mm]\phi(n,m) \in[/mm] H'
> E: goto programm, dass Eingabe immer mit m überschreibt
> und [mm]U_n[/mm] angesetzt auf m ausführt
> [mm]\phi[/mm] (n,m)= [mm]P_E[/mm]
> (n,m ) [mm]\in H^{\*}[/mm]
> <=>U(n,m) hält
> [mm]<=>U_n[/mm] angesetzt auf m hält
> [mm]\overbrace{<=>}^{?}[/mm] E hält bei Eingabe 0
> <=> [mm]U_{P_E}[/mm] hält bei EIngabe 0
> <=> [mm]\phi(n,m) \in[/mm] H'
Die Stelle mit dem Fragezeichen ist kein Problem: Für alle [mm] $k\in\IN_0$ [/mm] gilt: E (ich würde lieber [mm] $E_{n,m}$ [/mm] schreiben) hält bei Eingabe $k$ genau dann, wenn [mm] $U_n$ [/mm] bei Eingabe $m$ hält. Insbesondere gilt dies für $k=0$.
> bleibt zuzeigen:
> H [mm]\ge_{m}[/mm] H'
> Stecke ich ..;(
Das funktioniert mit der gleichen Idee wie [mm] $H\le_m [/mm] H'$ und [mm] $H^\*\le_m [/mm] H'$:
Sei für jedes [mm] $n\in\IN$:
[/mm]
[mm] $E_n:=$goto-Programm, [/mm] dass zunächst Eingabe mit 0 überschreibt und dann [mm] U_n [/mm] ausführt.
Dann bezeugt die Abbildung [mm] $t\colon\IN\to\IN$ [/mm] mit [mm] $t(n):=P_{E_n}$, [/mm] dass $H [mm] \ge_{m} [/mm] H'$.
|
|
|
|
