 |
 |
 |
 |
 |
 |
Startseite » Forum » Reduktion von einem Problem auf ein anderes
Reduktion von einem Problem auf ein anderes
Universität / Fachhochschule
Finanzmathematik
Tags: berechenbarkeit
 
|
  |
|---|
|
Guten Tag, Ich weis nicht ob ich mit meiner Frage hier richtig bin wen nicht bitte ich um verzeihung . Ich bin grade am üben für eine Klausur. Ich habe eine Sprache berechnet bei eingabe die Binärdarstellung von und das initiale Halteproblem gestartet mit leerem Band hält). Jetzt soll ich mit hilfe der Reduktion zeigen das unentscheidbar ist. (Ich weis das unentscheidbar ist.) also Also muss ich eine Funktion finden die ist. Meine Idee: wäre man startet auf dem Ersten Band mit der eingabe und prüfe ob ergebnis entspricht. wen ja dan akzeptiere. wen nein gehe in endlos schleife. und auf dem 2ten band starte mit der leeren eingabe. Ich wolte Fragen ob meine idee so richtig wäre und wen nicht, was daran nicht stimmt und um Hilfe bitten. Danke für eure Zeit. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, Sei eine Funktion, die für die Codierung für eine Turingmaschine berechnet, die sich folgendermaßen verhält: Auf Eingabe ignoriert diese zunächst und führt auf dem leeren Band aus. bezeichnet dabei die Turingmaschine, die durch codiert wird. Hält auf dem leeren Band so wird anschließend eine Turingmaschine auf angesetzt. Damit gilt: hält auf dem leeren Band schreibt die Bärdarstellung von auf das Band schreibt die Binärdarstellung von auf das Band und damit . Da unentscheidbar ist, muss auch unentscheidbar sein. Denn wäre entscheidbar so ließe sich mittels der obengenannten Reduktion ebenfalls entscheiden. Gruß Nick |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1553896
1553877