Funktioniert unser PC als Turingmaschine?

8

Funktioniert unser PC als Turingmaschine? Das Modell einer Turingmaschine besteht aus einem unendlichen Speicherband, was unendliche Zustände bedeutet. Angenommen, unser PC verfügt über 128 MB Speicher und 30 GB Festplatte, hat 256 ^ 30128000000 Zustände und somit endliche Zustände.

Ich weiß, dass wir eine Art Programm schreiben können, das, wenn uns während der Ausführung der Speicher ausgeht, anfordert, die Speicherplatte gegen eine leere Speicherplatte auszutauschen und die Ausführung fortzusetzen.

Aber was ist, wenn wir die Speicherplatte nicht austauschen ? Ist es in diesem Fall richtig, den PC als FA zu betrachten ?

siddstuff
quelle
Beachten Sie, dass selbst [große] Festplatten endlich sind und daher die darauf basierende Berechnung technisch als FSM dargestellt werden kann. sehr ähnlich zu dieser anderen Frage Turing vollständige und Rechenleistung
vzn
Ein Computer ist nicht auf den internen Speicher beschränkt. Es kann auch externen Speicher verwenden.
Reinierpost
Nein, es funktioniert als von Neumann-Maschine. Außerdem ist näher an der Unendlichkeit als erwartet. 25630128000000
Andrej Bauer
Turingmaschinen haben nicht unbedingt unendlich viel Speicher. Sie haben nur genügend Speicher, um alles zu tun, was Sie wollen. Wenn Sie sich darauf beschränken, Programme anzuhalten, kann eine Turing-Maschine auch über einen begrenzten Speicher verfügen. In beiden Fällen ist die Speichermenge, die eine Turingmaschine zu einem bestimmten Zeitpunkt benötigt, begrenzt, obwohl sie möglicherweise zunimmt. Vernetzte Computer haben auch eine begrenzte, aber möglicherweise zunehmende Speichermenge.
DanielV

Antworten:

11

Sie haben Recht, dass physische Computer über einen begrenzten Speicher verfügen und daher nicht vollständig sind. Es gibt andere Möglichkeiten, in denen die Berechenbarkeitstheorie kein gutes Modell für die Berechnung ist - sie berücksichtigt keine Zeit- und Speicherbeschränkungen. Die Komplexitätstheorie wurde (vielleicht) als realistischere Darstellung des Rechnens erfunden, aber IMHO leidet unter ähnlichen (aber subtileren) Problemen.

Andererseits müssen wir, um die Fähigkeiten und Grenzen des Rechnens mathematisch zu untersuchen, eine Abstraktion verwenden, die nicht eingeschränkt ist. Das macht die Analyse möglich. In ähnlicher Weise nehmen wir in der statistischen Mechanik an, dass die Anzahl der Elemente (Atome oder Moleküle) so groß ist, dass das Verhalten nahe an der Grenze liegt (dh wir lassen die Anzahl der Elemente gegen unendlich tendieren). Das Studium des Rechnens aus einer asymptotischen Perspektive hat ähnliche Vorteile, ist aber manchmal irreführend. Hier einige Beispiele für Letzteres:

  1. In der Kryptographie sind manchmal exponentielle Algorithmen möglich. Wenn wir die falschen Sicherheitsparameter wählen, ist unsere Verschlüsselung möglicherweise unsicher, obwohl sie "nachweislich sicher" ist.
  2. Polynom-Zeit-Algorithmen sollen effizientes und machbares Rechnen darstellen, aber viele von ihnen sind nicht machbar. Beispielsweise werden die ausgefeiltesten Matrixmultiplikationsalgorithmen in der Praxis nicht verwendet.
  3. Die moderne Komplexitätstheorie ist von der Worst-Case-Leistung besessen und kann keine heuristischen Algorithmen analysieren, die in der Praxis verwendet werden. NP-harte Probleme gelten als nicht realisierbar, werden jedoch in der Praxis ständig gelöst.

Ein weiteres Problem ist, dass echte Computer überhaupt nicht wie Turing-Maschinen funktionieren. Sie arbeiten wie RAM-Maschinen, die eine bessere Abstraktion für das eigentliche Rechnen darstellen.

Yuval Filmus
quelle
4

Ich denke, Sie haben die Antwort bereits selbst gegeben. Wenn der Hauptaspekt, über den Sie sich Sorgen machen, die (Un-) Endlichkeit von Zuständen ist, dann existiert eine Turingmaschine als solche nur als "hypothetisches Gerät".

Unabhängig davon, wie viel Speicher Sie Ihrem PC zur Verfügung stellen, ist dieser immer begrenzt. Daher können Sie Programme finden, die auf einer "echten" Turing-Maschine ausgeführt werden, jedoch aufgrund des begrenzten Bandes nicht auf diesem PC.

http://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines

Wache
quelle
Turingmaschinen haben eine potenziell unendliche Anzahl von Zuständen, aber eine universelle Turingmaschine kann jede Turingmaschine simulieren, während sie gleichzeitig eine feste Anzahl von Zuständen hat.
Yuval Filmus
7
@ YuvalFilmus Ich denke, Sie sind zwischen Zuständen und Konfigurationen verwechselt. Alle Turing-Maschinen haben endliche Zahlenzustände, aber aufgrund ihres unbegrenzten Speichers können diese in unendlich vielen Konfigurationen vorliegen. Auch universelle TMs haben nur endlich viele Zustände, benötigen jedoch möglicherweise unbegrenzten Speicher, um ihre Eingabemaschine zu simulieren.
AdrianN
1

Zu der Zeit, als die Turing-Maschinen erfunden wurden, waren Computer Frauen, die Berechnungen auf Altpapier durchführten. Das ist der Begriff der Berechnung, den Turingmaschinen ausdrücken. Ihr Band ist nicht mehr Teil von ihnen als Altpapier Teil einer Person, die Berechnungen durchführt.

Dies ist immer noch ein gutes Modell für die computergestützte Berechnung, da die Ressourcengrenzen in Computern normalerweise recht groß sind. Inhärent endliche Berechnungsmodelle werden nur dann nützlich, wenn die Anzahl möglicher Zustände sehr gering ist.

Reinierpost
quelle
-1

Ein moderner Computer ist Turing komplett, im Allgemeinen wird dieser Begriff mit Ausnahme von unendlichen Speichergeräten verwendet. In der Praxis kann der Speicher sehr lang sein. Beispielsweise werden wiederkehrende neuronale Netze mit Speicher (und wiederholtem Betrieb) als universelle Funktionsapproximatoren als vollständig bezeichnet. In der Tat bringen neuronale Turingmaschinen diese Idee auf eine Stufe, die weiter auf einfache Algorithmen schließen lässt.

Tolga Birdal
quelle
Wie beantwortet dies die Frage?
Raphael