2005 | OriginalPaper | Buchkapitel
Turingmaschinen, churchsche These und Ent-scheidbarkeit
verfasst von : Prof. Dr. Ingo Wegener
Erschienen in: Theoretische Informatik
Verlag: Vieweg+Teubner Verlag
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Aussagen zur Komplexität von Problemen und zur Effizienz von Algorithmen sind nur dann von allgemeiner Bedeutung, wenn sie nur unwesentlich von der verwendeten Programmiersprache und dem zugrunde liegenden Rechnertyp abhängen. Turingma-schinen werden sich als geeignetes Modell erweisen, um zu prüfen, welche Probleme berechenbar und welche Probleme in polynomieller Zeit lösbar sind. Turingmaschi-nen sind aber im Allgemeinen um nicht zu vernachlässigende polynomielle Faktoren langsamer als reale Rechner. Weit näher an reale Rechner angelehnt ist das Modell der Registermaschinen (random access machine = RAM). Wir werden dieses Modell hier vorstellen, um in Kapitel 2.3 zu zeigen, dass Turingmaschinen und reale Rechner sich gegenseitig ohne superpolynomiellen Zeitverlust simulieren können. Die konkreten Aussagen über die Laufzeit von Algorithmen beziehen sich in diesem Buch immer auf reale Rechner, das heißt wir bewerten arithmetische Operationen, Zuweisungen, Vergleiche, usw. als elementare Rechenschritte. Der schematische Aufbau einer Registermaschine ist in Abb. 2.1.1 dargestellt.