falscher(?) beweis für das Halteproblem |
| 12.10.2012, 01:08 | Auf diesen Beitrag antworten » | ||||
| Takirion | falscher(?) beweis für das Halteproblem Hallo, wir haben in der Schule in Info gerade die Turingmaschine und daraus resultierend auch das Halteproblem besprochen. Dazu hat er uns auch eine Beweisskizze gegeben, die grob so aussieht: Eine Turingmaschine kann maximal abzählbar unendlich viele verschiedene Eingaben entgegen nehmen, allerdings gibt es mehr als abzählbar viele Algorithmen, das heißt, es gibt nichteinmal eine Turingmaschine, die überhaupt alle Algorithmen (bzw. Kodierungen dieser) entgegennehmen könnte insbesondere also auch keine, die für jeden dieser Algorithmen das Halteproblem löst. Beide Behauptungen (abzählbar viele Eingaben, über-abzählbar viele Algorithmen) hat er uns im Prinzip einfach so ohne echten Beweis gegeben (wir haben uns auf Wikipedia die beiden Cantor-Diagonalisierungen angeschaut, was für ihn dann scheinbar so etwas wie ein Beweis war, den echten Zusammenhang hat er aber nicht hergestellt). Für die erste bin ich durchaus gewillt sie zu glauben (wobei mir beim Schreiben einfällt: Eigentlich müsste eine Turingmaschine auch unendlich lange Folgen von Nullen und Einsen entgegennehmen können, die Eingabe entspricht doch einfach nur der Anfangsbelegung der Felder auf dem unendlich langen Band der Turingmaschine...). Größere Probleme hatte ich mit der zweiten. Ich bin mir ziemlich sicher schon öfters gelesen zu haben, dass sich Turingmaschinen binär kodieren lassen. Wenn sich aber jede Turingmaschine binär kodieren lässt kann ich aber einfach genau diese binäre Kodierung als Eingabe verwenden bzw. kann es nur abzählbar viele verschiedene Turingmaschinen geben. Ich vermute, dass ein Problem in der Formulierung des Begriffs Algorithmus liegt. Im informatischen Sinne ist ein Algorithmus ja schlicht eine Turingmaschine. Mein Infolehrer hat sie uns als allgemein gültige Handlungsanweisung zur Lösung eines Problems definiert. Als ich ihn einmal auf dieses ganze Problem angesprochen habe, hat er so sinngemäß gesagt: "Es gibt doch über abzählbar viele Funktionen die Nullen und Einsen auf Nullen und Einsen abbilden." Darin liegt möglicherweise ein anderes Problem: Ist möglicherweise nur die Menge der Funktionen von {0,1}* auf {0,1}* überabzählbar (daran kein Zweifel), die Menge der berechenbaren Funktionen aber nicht? Es gibt ja durchaus nicht berechenbare Funktionen (Busy Beaver,...). Es wäre schön, wenn irgendjemand das hier mal zweifelsfrei klären könnte, was an meinen bzw. seinen Vermutungen richtig oder falsch ist. Vielen dank schonmal dafür. Lg Takirion |
||||
|
|
|||||
| 12.10.2012, 13:54 | Auf diesen Beitrag antworten » | ||||
| Karlito | Hallo, das ist harter Tobak! Das Halteproblem ist aus meiner Sicht zu schwer um es in der Schule zu behandeln. Ich glaube auch, dass die Annahmen deines Lehrers nicht stimmen: Man kann eine so genannte Universelle Turingmaschine definieren, welche endlich ist und alle! anderen Turinmaschinen simulieren kann. Dazu wird eine binäre Codierung der gewünschen Turingmaschine auf ein Band geschrieben und die universelle Turingmaschine simuliert dann die gewünschte spezielle Turingmaschine. Da sich jede dieser Turingmaschinen durch ein endliches Binärwort repräsentieren lässt, ist die Menge der Algorithmen (spezielle Turingmaschine) abzählbar. Bei den Eingabewörtern verhält es sich ähnlich. Man kann für jedes beliebige Eingabewort eine binäre Repräsentation finden. So sind diese prinzipiell auch abzählbar. Mittels Cantor-Diagonalisierung kann man nun zeigen, dass die Menge aller Kombinationen aus Turingmaschine und Eingabewort auch abzählbar ist. Die Annahme, dass irgendetwas in diesem Kontext überabzählbar ist, ist also falsch, sollte ich nichts übersehen haben. Das Halteproblem ist der Nachweis, dass es Probleme gibt, bei denen man nicht sagen kann ob eine Turingmaschine bei der Verarbeitung jemals anhält. Als Beweis führt man hier an, dass es unmöglich ist eine Turingmaschine anzugeben, welche kontrolliert, ob eine andere Turingmaschine anhält. Der Nachweis dafür geht aber weit über den Schulunterricht hinaus und ist auch nicht in 2 Seiten Text verständlich erklärbar. So, das ist erstmal alles was mir dazu einfällt. Fragen dazu kannst du natürlich gern weiterhin hier stellen. VG, Karlito |
||||
| 13.10.2012, 01:47 | Auf diesen Beitrag antworten » | ||||
| Takirion | Hi, danke bis hier hin schonmal, die Tatsache, dass die Menge der Turingmaschinen abzählbar ist war ja das, was mich am meisten interessiert hat. Trotzdem nochmal die zwei Fragen: 1. Die Menge der Funktionen, die 0,1 Strings auf 0,1 Strings abbilden ist definitiv überabzählbar. Daraus müsste ja folgen, dass es tatsächlich überabzählbar viel nicht berechenbare Funktionen gibt (denn die Menge der Turingmaschinen - also der berechenbaren Funktionen ist ja wie gerade gesehen abzälbar). Oder übersehe ich etwas? 2. Darf eine Turingmaschine auch unendlich lange Strings als Eingabe entgegennehmen? Und passend dazu: darf eine Turingmaschine auch unendlich viel Zustände haben? Lg Takirion |
||||
| 13.10.2012, 10:24 | Auf diesen Beitrag antworten » | ||||
| Karlito | Hallo Takirion,
Ich denke Du übersiehst nichts.
Eine Turingmaschine hat nur endlich viele Zustände. Bei den Eingaben bin ich mir nicht sicher. Ich denke potentiell kann man unendlich lange Eingabewörter betrachten, dann aber nur endlich lange Ausschnitte, bei der für jede Teilsequenz eine Turingmaschine ausgeführt wird. Ansonsten wäre das Halteproblem ja trivial, da die Maschine eh nie anhält. Ich hoffe ich konnte weiterhelfen. VG, Karlito |
||||
| Anzeige | |||||
|
|
|||||
| 16.10.2012, 18:12 | Auf diesen Beitrag antworten » | ||||
| Takirion | Müsste nicht die Universelle Turingmaschine unendlich viele Zustände haben? Wenn die universelle Turingmaschine nur n Zustände hat, dann überlege ich mir eine Turingmschine mit n+1 Zuständen, die eine Operation durchführt, die keine TM mit weniger als n+1 Zuständen ausführen kann (und sei es, dass ich sie als Busy Beaver TM mit n Zuständen betrachte und vor dem Halten in den Zustand n+1 gehen lasse und dann so weit nach rechts fahren lasse, bis sie noch eine 1 auf das Band schreiben kann) Diese könnte die universelle TM dann doch nicht simulieren oder doch? |
||||
| 16.10.2012, 19:08 | Auf diesen Beitrag antworten » | ||||
| Karlito | Hallo, die universelle Turingmaschine "merkt" sich auch, in welchem Zustand sich die zu simulierende TM befindet und passt diesen je nach Konfigurationsübergang an. Einfach gesprochen: Es ist ja auch möglich, eine Turingmaschine mit einem normalen Computer zu simulieren. Natürlich hat das gewisse Grenze. Ein unendlich langes Band hat ein Rechner ja eher nicht zur Verfügung. Was du dazu machen würdest, ist, dass du den aktuellen Zustand der TM in einer Variable speicherst, das Band in einer Liste und die Übergangsfunktionen in einer Tabelle. Der Rechner geht dann wie folgt vor: - Bandsymbol lesen - Zustand lesen - Übergangsfunktion auswerten (in Abhängigkeit vom Zustand und dem Bandsymbol) - Bandsymbol anpassen - Bandposition anpassen - Zustand anpassen. Wie vielleicht intuitiv klar ist, hat das Rechnerprogramm nur eine Begrenzte Anzahl an Zuständen, nämlich mit diversen Zwischenzuständen ungefähr die wie oben in der Liste. Die Turingmaschine, welche simuliert wird, hat jetzt wesentlich mehr Zustände, was jedoch egal ist, da auch jeder Zustand Simuliert wird. So wird auch die universelle Turingmaschine konstruiert. Die universelle Turingmaschine kann also Turingmaschinen mit beliebig vielen Zuständen simulieren. Sie selbst benötigt dafür nur eine konstante Anzahl an Zuständen, simuliert aber alle Zustände der gewünschten TM. VG, Karlito |
||||
|
|
