Turing-Vollständigkeit

Turing-Vollständigkeit bezieht sich auf eine Maschine, die, wenn sie genügend Zeit und Speicherplatz sowie die erforderlichen Anweisungen hat, jedes noch so komplexe Rechenproblem lösen kann. Der Begriff wird normalerweise zur Beschreibung moderner Programmiersprachen verwendet, da die meisten von ihnen Turing-Vollständigkeit aufweisen (C++, Python, JavaScript usw.).

Was ist eine Turing-Maschine?
Bevor es moderne Computer gab, stellte Alan Turing die Hypothese auf, dass es eines Tages eine Maschine geben würde, die jedes Problem lösen könnte. Diese Maschine wurde als Turing-Maschine bekannt.

Alan stellte sich seine Maschine als ein langes Stück Band vor, auf dem Informationen in Form von Binärcodes (1en und 0en) geschrieben sind. Die Maschine würde auch einen Lese-/Schreibkopf haben, der sich entlang des Bandes bewegt und jedes Quadrat einzeln liest. Der Code würde der Maschine ein Rechenproblem stellen, und das Band wäre so lang wie nötig, um eine Lösung zu finden.

Während sich der Kopf über das Band bewegt, folgt die Maschine einfachen Anweisungen, die ihr Verhalten bestimmen. Sie liest das Band, folgt den Anweisungen und führt eine bestimmte Aktion aus, um einen neuen Code zu schreiben, während sie sich fortbewegt. Dieses neue Codemuster ist die Antwort auf das Problem. Turings hypothetische Maschine könnte jedes Rechenproblem lösen, das in Code ausgedrückt werden kann (und eine berechenbare Antwort hat).

Ein Gerät oder eine Programmiersprache gilt als turing-vollständig, wenn es/sie eine Turing-Maschine replizieren kann, indem es/sie jedes Programm ausführt oder jedes Problem löst, das die Turing-Maschine ausführen oder lösen könnte. Ist ein Gerät oder eine Programmiersprache hingegen nicht in der Lage, dies zu tun, so gilt es als unvollständig nach Turing.

Ein einfacher Taschenrechner ist ein Beispiel für ein System, das unvollständig nach Turing ist, da es nur einige wenige Arten von Berechnungen durchführen kann. Im Gegensatz dazu kann ein programmierbarer wissenschaftlicher Taschenrechner (der alle Arten von Berechnungen durchführen kann) als Turing-Maschine bezeichnet werden.

Blockchain und Turing-Vollständigkeit
Während einige Anwendungen der Blockchain-Technologie Turing-Vollständig sind, sind andere Turing-Unvollständig. Dies hängt von der verwendeten Skripting-Technologie ab. Die in Bitcoin verwendete Skriptsprache ist beispielsweise absichtlich als Turing-Unvollständig konzipiert, da sie ihren Zweck erfüllt und eine höhere Komplexität potenziell zu Problemen führen würde. Indem sie einfach gehalten wird, können die Entwickler mit hoher Genauigkeit vorhersagen, wie sie in der begrenzten Anzahl von Situationen, in denen sie verwendet wird, reagieren wird.

Ethereum hingegen ist als eine Turing-Vollständige Blockchain konzipiert. Dies ist wichtig, weil es die Vereinbarungen, aus denen Smart Contracts bestehen, verstehen muss. Durch die Turing-Vollständigkeit ist Ethereum in der Lage, jede künftige Vereinbarung zu verstehen und umzusetzen, auch solche, an die man noch gar nicht gedacht hat. Mit anderen Worten: Die Turing-Vollständigkeit von Ethereum bedeutet, dass es mit seiner Codebasis praktisch jede Aufgabe ausführen kann, solange es über die richtigen Anweisungen, genügend Zeit und Rechenleistung verfügt.

« Zurück zum Glossar Index