https://kryptowiki.eu/index.php?action=history&feed=atom&title=Turing-Vollst%C3%A4ndigkeitTuring-Vollständigkeit - Versionsgeschichte2026-05-13T00:07:28ZVersionsgeschichte dieser Seite in Kryptowiki - Die freie Enzyklopädie der KryptowährungenMediaWiki 1.39.15https://kryptowiki.eu/index.php?title=Turing-Vollst%C3%A4ndigkeit&diff=2478&oldid=prevC1ph4: Die Seite wurde neu angelegt: „Mit '''Turing-Vollständigkeit''' eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform ''Turing-vollständig'' wird synon…“2018-05-22T16:53:21Z<p>Die Seite wurde neu angelegt: „Mit '''Turing-Vollständigkeit''' eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform ''Turing-vollständig'' wird synon…“</p>
<p><b>Neue Seite</b></p><div>Mit '''Turing-Vollständigkeit''' eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform ''Turing-vollständig'' wird synonym häufig auch ''turingmächtig'' verwendet. Der Name ist abgeleitet vom englischen Mathematiker [[Alan Turing]], der das Modell der [[Turingmaschine|universellen Turingmaschine]] eingeführt hat.<ref>{{Literatur |Autor=[[Alan Turing]] |Titel=On Computable Numbers, with an Application to the Entscheidungsproblem |Sammelwerk=Proceedings of the London Mathematical Society |Band=Bd.&nbsp;s2-42 |Nummer=1 |Datum=1937 |Seiten=230–265 |Online=[http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf PDF] |DOI=10.1112/plms/s2-42.1.230}}</ref><ref>{{Literatur |Autor=[[Alan Turing]] |Titel=On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction |Sammelwerk=Proceedings of the London Mathematical Society |Band=Bd.&nbsp;s2-43 |Nummer=1 |Datum=1938 |Seiten=544–546 |Online=[http://www.dna.caltech.edu/courses/cs129/caltech_restricted/Turing_1937_correction_IBID.pdf PDF] |DOI=10.1112/plms/s2-42.1.230}}</ref><br />
<br />
== Definition und Anwendung des Begriffs ==<br />
Exakt ausgedrückt bezeichnet Turing-Vollständigkeit in der [[Berechenbarkeitstheorie]] die Eigenschaft einer [[Programmiersprache]] oder eines anderen logischen Systems, sämtliche Funktionen berechnen zu können, die eine universelle Turingmaschine berechnen kann. Anders ausgedrückt, das System und eine universelle Turingmaschine können sich gegenseitig [[Emulator|emulieren]]. Noch vor der Prägung des Begriffs wurde der erste turingmächtige mathematische Formalismus von [[Kurt Gödel]] im Jahre 1931 in seiner Arbeit zum [[Gödelscher Unvollständigkeitssatz|Unvollständigkeitssatz]] veröffentlicht.<br />
<br />
Obwohl solche Maschinen physikalisch unmöglich sind, da sie unbegrenzten Speicherplatz besitzen müssten, werden gängige Programmiersprachen und Computer, die universell wären, wenn sie unbegrenzten Speicher besäßen, als Turing-vollständig bezeichnet. Die [[Analytical Engine]] von [[Charles Babbage]] wäre in diesem Sinne Turing-vollständig gewesen, wenn sie jemals gebaut worden wäre.<ref>{{Literatur |Autor=J. Fuegi, J. Francis |Titel=Lovelace & Babbage and the creation of the 1843 “notes” |Sammelwerk=Annals of the History of Computing |Band=Bd.&nbsp;25 |Nummer=4 |Verlag=IEEE |Datum=2003-10 |ISSN=1058-6180 |Seiten=16–26 |DOI=10.1109/MAHC.2003.1253887}}</ref><br />
<br />
Die [[Zuse Z3]] wurde 1941 gebaut, sie war nicht turingmächtig konstruiert und wurde auch nicht dafür genutzt.<ref>{{Literatur |Autor=Raúl Rojas |Titel=Konrad Zuse’s Legacy: The Architecture of the Z1 and Z3 |Sammelwerk=IEEE Annals of the History of Computing |Band=Bd.&nbsp;19 |Nummer=2 |Datum=1997 |ISSN=1058-6180 |Seiten=5–16 |Online=[http://ed-thelen.org/comp-hist/Zuse_Z1_and_Z3.pdf PDF]}}</ref> Wie [[Raúl Rojas]] im Jahr 1998 herausfand, ist sie über zwei Tricks (begrenzte Rechengenauigkeit und Zusammenkleben des Lochstreifens zu einer Schleife) dennoch Turing-vollständig, wird dabei aber sehr langsam.<ref>{{Literatur |Autor=[[Raúl Rojas]] |Titel=How to make Zuse’s Z3 a universal computer |Sammelwerk=Annals of the History of Computing |Band=20 |Nummer=3 |Verlag=IEEE |Datum=1998 |ISSN=1058-6180 |Seiten=51–54 |Online=[http://www.inf.fu-berlin.de/~rojas/1997/Universal_Computer.pdf PDF Scan], [http://citeseerx.ist.psu.edu/viewdoc/download;?doi=10.1.1.37.665&rep=rep1&type=pdf PDF], [https://web.archive.org/web/20140803115857/http://www.zib.de/zuse/Inhalt/Kommentare/Html/0684/universal2.html HTML] |DOI=10.1109/85.707574}}</ref><br />
<br />
Im Jahre 1954 veröffentlichte [[Hans Hermes]] als einer der ersten einen Beweis für die Turing-Vollständigkeit von [[Von-Neumann-Architektur|Von-Neumann]]-Rechenmaschinen, also von tatsächlich realisierten Computern. Alle modernen Computer sind ebenfalls im weiteren Sinne Turing-vollständig.<br />
<br />
Eine Maschine, die Turing-vollständig ist, kann jede Berechnung, die ''irgendein'' Computer ausführen kann, ebenso ausführen und wird daher auch als ''universell programmierbar'' bezeichnet. Hierdurch ergibt sich jedoch weder eine Aussage über den Aufwand, ein bestimmtes Programm auf einer solchen Maschine zu [[Implementierung|implementieren]], noch über die Zeit, die zur Ausführung benötigt werden würde.<br />
<br />
Die [[Berechenbarkeitstheorie]] befasst sich damit, welche Probleme mit Hilfe einer Maschine, insbesondere mit einer Turingmaschine, lösbar sind.<br />
<br />
== Beispiele ==<br />
Die gängigen [[Programmiersprache]]n sind Turing-vollständig. Dies schließt konventionelle [[Prozedurale Programmiersprache|prozedurale Sprachen]] wie [[C (Programmiersprache)|C]] und [[Objektorientierte Programmierung|objektorientierte]] Sprachen wie [[C++]] und [[Java (Programmiersprache)|Java]] ein. Auch Sprachen, die nach weniger geläufigen [[Programmierparadigma|Paradigmen]] entworfen wurden, unter anderem [[funktionale Programmiersprache]]n wie [[LISP]] und [[Haskell (Programmiersprache)|Haskell]] und Sprachen für [[Logikprogrammierung]] wie [[Prolog (Programmiersprache)|Prolog]], sind Turing-vollständig. Ebenfalls Turing-vollständig sind die in der Berechenbarkeitstheorie verwendeten, minimalistischen Programmiersprachen [[GOTO-Programm|GOTO]] und [[WHILE-Programm|WHILE]].<br />
<br />
Beispiele für nicht Turing-vollständige Programmiersprachen zu finden, fällt Fachleuten schwer, da diese die Sprachen nach Funktionalität filtern und strukturelle Sprachen und rein prozess-orientierte von vornherein als sehr eingeschränkt erachten und sie gar nicht erst in die Betrachtung aufnehmen. Ein häufig diskutiertes Beispiel sind [[Standard Generalized Markup Language|SGML]]-Dialekte und -Derivate wie beispielsweise [[Hypertext Markup Language|HTML]], die [[Auszeichnungssprache]] zur Darstellung von [[Webseite]]n. Diese Struktur-Sprache ist bei Einsatz aller gegebenen Attribute durchaus in der Lage, universelle Beschreibungen für Prozesse zu halten. Auch die zeit-diskrete Steuerung bzw. die zeitliche Abfolge lässt sich mit Hilfe der Relationalen beschreiben. Alle Instrumentale, die nötig wären, sind im Sprachschatz vorhanden. Einziges Hindernis zur Aufnahme in die Reihe der Turing-vollständigen Sprachen stellt die Tatsache dar, dass HTML in sich nicht aktiv sein kann. Erst in Ergänzung um eine aktive Komponente, wie z.&nbsp;B. [[JavaScript]], oder durch den ausführenden [[Webbrowser]] ergibt sich die Steuerbarkeit und verfolgbare zeitliche und hierarchische Abhängigkeit.<br />
<br />
Einige Autoren definieren den Begriff „Programmiersprache“ auf Basis der Turing-Vollständigkeit.<ref>So etwa {{Literatur |Autor=Bruce MacLennan |Titel=Principles of Programming Languages |Verlag=Oxford University Press |Ort=New York |Datum=1999 |ISBN=0-19-511306-3 |Seiten=1}}</ref><br />
<br />
Eine Folge von [[Formel]]n in einer [[Tabellenkalkulation]] ohne [[Schleife (Programmierung)|Schleife]] ist nicht Turing-vollständig, obwohl es möglich ist, komplexe Operationen mit einem solchen System durchzuführen. Dagegen ist z.&nbsp;B. die [[Makro]]sprache [[Visual Basic for Applications|VBA]] für [[Microsoft Excel]] ihrerseits Turing-vollständig.<br />
<br />
[[Regulärer Ausdruck|Reguläre Ausdrücke]] in Programmiersprachen, [[Editor (Software)|Editoren]] oder Systemwerkzeugen (z.&nbsp;B. [[grep]]), wo sie vor allem zum [[Pattern Matching]] verwendet werden, sind nicht Turing-vollständig, auch wenn in vielen Implementierungen reguläre Ausdrücke um Konstrukte wie Rückwärtsreferenzen (engl. ''{{lang|en|backreferences}}'') erweitert werden, die nicht mehr von [[Endlicher Automat|endlichen Automaten]] erzeugt werden können.<br />
<br />
Die [[Relationale Algebra]] ist nicht Turing-vollständig, da es innerhalb dieser nicht möglich ist, die [[Transitive Hülle (Relation)|transitive Hülle]] zu bilden. Außerdem verfügt die Relationale Algebra nicht über Schleifen.<br />
<br />
Eine wichtige Schlussfolgerung aus der Berechenbarkeitstheorie ist, dass es keinen Algorithmus geben kann, der über jedes in einer bestimmten Turing-vollständigen Programmiersprache geschriebene Programm aussagen kann, ob es in endlicher Zeit abbricht oder für immer in einer Schleife bleibt (siehe [[Halteproblem]]). Eine Methode, dieses Problem zu umgehen, ist das Abbrechen eines Programmablaufs nach einer fixen Zeitspanne oder das Herabsetzen der Mächtigkeit von Kontroll-Anweisungen. Solche Systeme gelten jedoch strikt als nicht Turing-vollständig. Dieses Resultat wurde z.&nbsp;B. von [[Lawrence Landweber|Landweber]] abgeleitet.<br />
<br />
Ein weiteres Theorem stammt aus der Berechenbarkeitstheorie. Mit einer Maschine, die nur endliche Schleifen bietet (zum Beispiel [[LOOP-Programm|LOOP]] oder die dazu äquivalenten [[Primitiv-rekursive Funktion|Primitiv-rekursiven Funktionen]]), ist garantiert, dass jedes Programm irgendwann anhält. Mit dieser Maschine können jedoch nicht alle Probleme gelöst werden, die von einer Turing-Maschine gelöst werden können, z.&nbsp;B. die [[Ackermann-Funktion]].<br />
<br />
[[Μ-Rekursion|μ-rekursive Funktionen]] sind Turing-vollständig (daher kommt auch die Bezeichnung ''rekursiv'' für [[entscheidbar]]e Mengen)<br />
<br />
Der [[Typisierung (Informatik)|untypisierte]] [[Lambda-Kalkül]] ist Turing-vollständig, aber viele typbehaftete [[Kalkül]]e, unter anderem System F, sind es nicht. Der Vorteil von typbehafteten Systemen ist ihre Möglichkeit, die meisten typischen Computerprogramme darzustellen, dabei aber mehr Fehler entdecken zu können.<br />
<br />
== Literatur ==<br />
* Walter S. Brainerd, Lawrence H. Landweber: ''Theory of Computation.'' Wiley, New York NY u.&nbsp;a. 1974, ISBN 0-471-09585-0.<br />
<br />
== Externe Links ==<br />
* [http://homepages-fb.thm.de/boergens/marken/briefmarke_05_01.htm Turingseite] der Technischen Hochschule Mittelhessen<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
{{SORTIERUNG:Turing Vollstandigkeit}}<br />
[[Kategorie:Berechenbarkeitstheorie]]<br />
[[Kategorie:Alan Turing]]</div>C1ph4