Turing vollständige und Rechenleistung

In einer Vorlesung erwähnte ein Professor, dass moderne Computer nicht so viel Rechenleistung haben wie eine Turing-Maschine, weil sie nicht unendlich viel Speicher haben. Da kein Computer unendlich viel Speicher haben kann, ist die Turing-Maschine daher unerreichbar und stellt lediglich die Obergrenze dar des Rechnens. Gibt es ein Maß oder eine Definition dafür, welche Probleme (oder Problemklassen) sich aus diesem Grund unserer Rechenleistung entziehen?

Wenn wir das Universum als endlich betrachten, dann liegt alles, was mehr Speicher als diese endliche Menge benötigt, außerhalb unserer Rechenfähigkeiten.

Dies ist jedoch kein gutes Modell für das Studium der Berechenbarkeit, da das Turing-Maschinenmodell in der Realität viel besser funktioniert und wir es daher für das Studium der Berechnung auf realen Computern verwenden. Eine Turing-Maschine benötigt nicht wirklich unendlich viel Speicher, sondern nur unbegrenzt viel Speicher. Zum Beispiel können wir einem Computer mit der Zeit zusätzlichen Speicher zur Verfügung stellen (da der Computer immer mehr Speicher benötigt) und dann haben wir etwas Ähnliches wie eine Turing-Maschine. Wenn wir davon ausgehen, dass wir unbegrenzt viel Zeit und Speicher haben, um unsere Berechnung abzuschließen, fängt die Turing-Maschine dieses Konzept der Berechnungsfähigkeit im Prinzip recht gut ein.

Im Wikipedia-Artikel über Turing-Maschinen finden Sie einen Abschnitt , in dem die Relevanz des Modells erörtert wird.

Wenn Sie an einer realisierbaren Berechenbarkeit interessiert sind , ist die Komplexitätstheorie (bei der wir verschiedene Ressourcen wie Zeit und Raum für die Ausführung einer Rechenaufgabe berücksichtigen) näher an dem, was wir in der Praxis wirklich tun können als die Berechenbarkeitstheorie. Viele Experten geben an, dass die durchführbaren Berechnungen in die Komplexitätsklasse (und in jüngerer Zeit in probabilistischen und Quantenversionen von , dh und ).P B P P B Q P$\mathsf{P}$$\mathsf{P}$$\mathsf{BPP}$$\mathsf{BQP}$

Sie könnten Linear Bounded Automaton in Betracht ziehen und die entsprechenden Sprachen sind die kontextsensitiven Sprachen . Sehen Sie in der Chomsky-Hierarchie nach, welche Sprachen für solche Automaten unerreichbar sind.

Übrigens sind aufgrund der eingeschränkten Rechenleistung einige "nicht erreichbare" Probleme in greifbare Nähe gerückt!

Zum Beispiel ist das Problem des Anhaltens für Turing-Maschinen nicht zu entscheiden, aber es ist für Automaten mit linearer Begrenzung zu entscheiden.

Die Berechnungstheorie ist eine Abstraktion der realen Welt. In vielerlei Hinsicht passt die Abstraktion nicht in die reale Welt. Zum einen können wir keine Computer mit unbegrenztem Speicher herstellen. Wir können also nicht einmal Maschinen bauen, um beliebige reguläre Sprachen zu erkennen - oder sogar beliebige endliche Sprachen!

Dies ist jedoch kein allzu großes Problem. In der realen Welt können wir nicht einmal Eingaben beliebiger Größe konstruieren, und selbst wenn wir könnten, wären wir nicht lange genug da, um die Antwort zu sehen.

Im engeren Sinne also nein: Die Klasse der physikalisch realisierbaren Computer ist strikt weniger leistungsfähig als die Klasse der Turing-Maschinen. Es ist auch weniger mächtig als die Klasse der endlichen Automaten.