Äquivalenzproblem < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Begründen Sie algorithmisch mit Hilf des Halteproblems, warum das Äquivalenzproblem nicht entscheidbar ist. |
Hi Leute!
Ich hab zu dieser Aufgabe dieses Bild gemalt: http://s7.directupload.net/file/d/3299/dz8ux7or_jpg.htm
Ich kapiere aber nun mein eigenes Bild nicht so richtig.
Wir nehmen an, dass Äquivalenzproblem sei entscheidbar (Entscheider A). Der Entscheider A erhält die Turingmaschinen jeweils in Form einer Gödelnummer als Eingabe.
TM : akzeptiert alles -> Ausgabe des Entscheiders: ja
TM : ?
Wie geht es hier nun weiter? Was ich nämlich an meinem eigenen Bild nicht kapiere, ist, welche Eingabe der Benutzer machen darf! Ich hab die große Box (die, die das allgemeine Halteproblem darstellen soll) und eine kleine Box (die, die den Entscheider für das Äquivalenzproblem darstellen soll). Wenn ich nun Benutzer dieser Black-Box bin, wo darf ich die Eingabe eingeben? Nur an der großen Box außen? Oder kann der Benutzer auch Eingaben an der inneren Box dem Entscheider eingeben? Was sind meine Eingaben? Wo kann ich die richtige Eingabe an meiner Aufgabe ablesen?
Wenn der Benutzer nur an der äußeren Box (allgemeines Halteproblem) Eingaben eingeben darf (was ich vermute!), was passiert, dann mit der Eingabe? Hier wäre die Eingabe ja (so ist die Eingabe ja im allgemeinen Halteproblem spezifiziert; zumindestens in unserer Vorlesung); wie aber wird dann das zu ? Geschieht im inneren der Box für das allgemeine Halteprobleme eine Art "Umanwandlung" von zu ? Wie muss ich mir das vorstellen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:56 Fr 28.06.2013 | | Autor: | bandchef |
Ich pushe meine Fragen ungerne, aber kann mir wirklich niemand meine Fragen beantworten?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:47 So 30.06.2013 | | Autor: | Anna-Lyse |
> Ich pushe meine Fragen ungerne, aber kann mir wirklich
> niemand meine Fragen beantworten?
Naja, Du hast die Skizze selbst erstellt - Du solltest am Besten wissen, wie sie gemeint ist und worauf sie hinauslaufen soll ;) Von daher Fragen dazu wohl eher weniger, Fragen/Tipps zur Aufgabenstellung wohl schon eher.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Sa 29.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
