Author

Topic: Turing-Vollständigkeit (Read 1341 times)

full member
Activity: 159
Merit: 100
January 19, 2015, 08:15:48 AM
#10
Hallo dewdeded,

TL; DR: Es gibt keine (un-)vollständige Turing-Vollständigkeit! Turingvollständigkeit kann auch für real existierende Systeme gelten und ist in der Praxis durch das "One-Size-Fits-All"-Schema in der Computerchip-Branche eher die Regel als die Ausnahme.


Genau, denn vollständige Turing-Vollständigkeit in einer Kryptowährung führt ja mindestens zu folgenden Sicherheitsgefahren:

Hast du Gyrsurs Beitrag überhaupt gelesen?

http://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeit

Quote
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 emulieren.

Auch wenn ich kein Freund von der deutschen Wikipedia bin, so ist der von ihm zitierte Abschnitt bereits die Antwort. Deshalb dachte ich eigentlich, dass das allgemein verstanden wäre.

Wenn du also von einer "vollständigen Turing-Vollständigkeit" schreibst, dann musst du dir auch die folgende Frage gefallen lassen: Was ist unvollständige Turing-Vollständigkeit?

Vorsicht, das ist eine Fangfrage! Die Antwort ist einfach die, dass es keine (un-)vollständige Turing-Vollständigkeit gibt! Es gibt Turing-Vollständigkeit. Aber es gibt keine Abstufung dazu.

Die Turingvollständigkeit (engl. turing completeness) ist auch unter dem Namen Turingmächtigkeit (engl. turing powerful) bekannt, was hoffentlich etwas weniger verwirrend klingt. Es geht darum, dass die betrachtete Turingmaschine genügend Macht (im Sinne von Möglichkeiten) besitzt, um eine andere Turingmaschine zu simulieren. Auf den Zusammenhang kommt es an: Wenn eine Turingmaschine eine beliebige andere Turingmaschine simulieren kann, dann ist sie universell genug, um jedes denkbare und als Algorithmus formulierbare Problem zu lösen. Das ist das ausschlaggebende Argument für praktische Anwendungen und notwendige Bedingung für die Klassifikation als turingmächtiges System.

Der Schnickschnack mit dem unendlichen Band ist nur ein Kunstgriff, damit man nicht mit so schwammigen Begriffen wie "genügend großes Band" arbeiten muss und dann beim Beweisen mit der begrenzten Kapazität zu kämpfen hat. Hier haben sich also die Theoretiker verständlicherweise das Leben leichter gemacht. Es geht aber insbesondere in der praktischen Betrachtung nur darum, ob man ein System mit einem anderen System simulieren oder emulieren kann. Mehr nicht.

Falls nämlich das unendliche Band ausschlaggebend wäre, dann gäbe es in der Praxis keine turingmächtigen Systeme und dementsprechend hätte diese Klasse nur noch theoretische aber keine praktische Relevanz mehr.

Jedoch werden gängige Programmiersprachen wie z.B. Java, C/C++, C# und PHP als turingmächtige Programmiersprachen gehandelt (man kann z.B. einen Java-Bytecode-Compiler in C schreiben und umgekehrt; außerdem ist z.B. C mächtig genug um einen Interpreter für Java-Bytecode zu implementieren: die JVM).

Außerdem gibt es auch klar ersichtliche Anwendungen, welche turingmächtig sein müssen: Betriebssysteme, virtuelle Maschinen und Emulatoren. Im Allgemeinen ist es also bereits hinreichend (aber nicht notwendig!), wenn man auf Loopmächtigkeit prüft und bei negativem Resultat von einer Einstufung als "Turingmächtig" ausgeht. Ein guter Test ist halt die Implementierung des Klassikers: die Ackermann-Funktion. Ist also die Ackermann-Funktion implementierbar, so ist das System mächtiger als loopmächtig, was im praktischen Bereich bereits hinreichend für die begründete Annahme eines turingmächtigen Systems ist.

Insofern ist der Wikipedia-Artikel nicht ganz optimal geschrieben, auch wenn dieser eigentlich genau das oben Geschilderte ausdrückt:
http://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeit

Quote
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.

Gruss,
Bill

Tante Edith mal wieder: TL; DR war zu schwammig gehalten.
legendary
Activity: 2856
Merit: 1520
Bitcoin Legal Tender Countries: 2 of 206
January 18, 2015, 03:51:39 PM
#9

Many may not be aware of Automated Transactions or AT (http://ciyam.org/at) but it is a "Turing complete" VM for transactions that can have "state" and perform "other transactions in a trustless and deterministic manner".

Quote
What it does is basically the same as Ethereum *except* that AT has been designed to be added to *any blockchain system*.

http://ciyam.org/at
legendary
Activity: 1232
Merit: 1011
Monero Evangelist
January 18, 2015, 03:39:03 PM
#8
legendary
Activity: 1232
Merit: 1011
Monero Evangelist
January 18, 2015, 02:34:03 PM
#7
Meiner Meinung nach ist es weniger die Leistungsfähigkeit als die (von Dir ebenfalls angesprochene) Sicherheit, die wirklich entscheidend ist und Turing-vollständige Kryptowährungen grundsätzlich problematisch macht.
Genau, denn vollständige Turing-Vollständigkeit in einer Kryptowährung führt ja mindestens zu folgenden Sicherheitsgefahren:

- Angreifer Bob stielt von Service-Betreiber Alice Geld ("Ether")
- Angreifer Bob stielt von Service-Betreiber Alice den Service (zahlt seine "Ether"-Fees nicht korrekt)
- Angreifer Bob DDOS'ed Alices Service finanziell
(verbraucht fremdes "Ether" ohne eigenen Nutzen, rein destruktiv, Beispiel: 100000000x starten eines Services der Alice "Ether" kostet)
- Angreifer Bob DDOS'ed Alices Service durch klassische Überlastung (hardwareseitig Vollauslastung, softwareseitige Vollauslastung, Mischformen, Deadlocks, etc.)
- durch Fehler im Protokoll oder Bugs in der Softwareimplementierung wird "Ether" ungewollt zerstört/geht verloren
(Gefahr die zwar jede Coin in sich trägt, aber eben durch Turing-Vollständigkeit enorm steigt)


Und eben wegen dieser Gefahren, wird a) Ethereum ewig Vaporware/in der Entwicklung bleiben oder b) nie volle Turing-Vollständigkeit erhalten und manche sagen eben, überhaupt erhalten können.


(So wurde es mir erklärt, ich hoffe dass es so stimmt.)

legendary
Activity: 1153
Merit: 1012
January 18, 2015, 02:09:00 PM
#6

EDIT: meine persönliche meinung ist, dass das konzept einfach einige jahre zu früh kommt, weil die hardware noch nicht soweit ist. das ist praktisch noch nicht umsetzbar mit dem heutigen stand der technologie.

Meiner Meinung nach ist es weniger die Leistungsfähigkeit als die (von Dir ebenfalls angesprochene) Sicherheit, die wirklich entscheidend ist und Turing-vollständige Kryptowährungen grundsätzlich problematisch macht.
legendary
Activity: 2856
Merit: 1520
Bitcoin Legal Tender Countries: 2 of 206
January 18, 2015, 06:48:31 AM
#5
http://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeit

Quote
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 emulieren.

hatten wir im grundstudium theoretische informatik in berechenbarkeitstheorie. man kann alles berechnen wenn man unbegenzten speicherplatz voraussetzt. die programmiersprache und die rechnerarchitektur (PC --> Von-Neumann-Architektur) besitzen alle nötigen voraussetzungen (sprachelemente, rechnerarchitektur) um jedes problem, welches man formal beschreiben kann, berechnen zu können.

http://de.wikipedia.org/wiki/Formale_Sprache

Bitcoin kann das nicht, da das Protokoll keine sprachelemente zur verfügung stellt um das zu bewerkstelligen. das protokoll ist zweckgebunden. damit reduziert sich aber auch der anspruch auf resourcen und die sicherheit erhöht sich.

ethereum stellt eine sprache zur verfügung welche alle probleme, welche sich formal beschreiben lassen, berechnen kann wenn unendliche resourcen zur verfügung stehen. das muss aber erst bewiesen werden! sprachelemente ist die eine sache. performance und skalierbarkeit in einer verteilten umgebung eine andere sache.

EDIT: meine persönliche meinung ist, dass das konzept einfach einige jahre zu früh kommt, weil die hardware noch nicht soweit ist. das ist praktisch noch nicht umsetzbar mit dem heutigen stand der technologie.
legendary
Activity: 1270
Merit: 1000
January 18, 2015, 06:44:20 AM
#4
Das ungefähr so, als wäre eine Frau nicht ganz schwanger. Entweder ein System ist Turing-Vollständig oder es erfüllt die damit verbundenen Kriterien nicht. Das wesentliche Unterscheidungsmerkmal ist halt die Abgrenzung zur Loop-Mächtigkeit.

Worauf dewdeded hinauswill dürfte dieses hier sein:

http://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeit

Quote
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.

full member
Activity: 159
Merit: 100
January 18, 2015, 06:29:38 AM
#3
Hallo dewdeded,

Das führt dich jetzt zu welcher Frage?

bezogen auf:
- zum Thema Komplexität & Unmöglichkeit der Turing-Vollständigkeit die Informatiker die gesprochen habe, gehen alle davon aus, dass diese nicht vollständig umgesetzt wird, sondern ewig das (Design-)Ziel (& Marketing-Claim) bleibt aber nie komplett erreicht wird/werden soll

Das ungefähr so, als wäre eine Frau nicht ganz schwanger. Entweder ein System ist Turing-Vollständig oder es erfüllt die damit verbundenen Kriterien nicht. Das wesentliche Unterscheidungsmerkmal ist halt die Abgrenzung zur Loop-Mächtigkeit.

Die Frage ist also: Ist Ethereum turing-vollständig? Sofern jemand Beispiele wie z.B. "Ethereum in einem Knoten von Ethereum implementieren" oder die Ackermann-Funktion umsetzen kann, ist diese Frage klar zu bejahen. Alles andere ist einfach sachlich falsch und verwirrend.

Edith: Sätze auf Verständlichkeit hin verändert.
legendary
Activity: 1232
Merit: 1011
Monero Evangelist
January 18, 2015, 06:16:03 AM
#2
Das führt dich jetzt zu welcher Frage?
full member
Activity: 159
Merit: 100
January 18, 2015, 06:08:13 AM
#1
Fortsetzung von diesem Beitragsstrang.

Das ist kein wissenschaftlich vollständiger Artikel. Es wurde vielmehr auf Lesbarkeit und Verständlichkeit eines sehr komplexen Themas geachtet.

Kurz die allgemeine Definition: Eine turing-vollständige Turingmaschine ist ein Maschinenmodell, welches jede beliebige Turingmaschine simulieren kann. Sogar sich selbst.

Praktisch betrachtet:
Bis etwa 1928 glaubte die Informatikwelt, dass alles mit loop-mächtigen Maschinenmodellen berechenbar wäre. Das sind Maschinenmodelle, welche beim Betreten einer auszuführenden Schleife bereits die Anzahl der Schleifenwiederholungen kennen (z.B. for (int i=0; i < 10; i++) { ... }: Ganz klar nur zehn Durchläufe (0 bis 9)).

1928 wurde die Ackermann-Funktion vorgestellt, welche eben mit einem solchen Maschinenmodell nicht mehr berechenbar ist und damit ein Gegenbeispiel zur damals herrschenden Lehrmeinung darstellte.
Weitere moderne Beispiele sind Betriebssysteme und Virtualisierungsumgebungen.

Auswirkungen:
Solange die (Höchst-)Anzahl der Schleifendurchläufe beim Betreten der Schleife bekannt ist, kann die Korrektheit eines Programms bewiesen werden. Bei vollständig loop-mächtigen Programmen wäre es also durchaus möglich, fehlerfreien Code zu garantieren. Deshalb sind loop-mächtige Programmbestandteile interessant für praktische Korrektheitsbeweise von Programmen.

Sobald das aber im Bereich der turing-vollständigen Maschinenmodelle stattfindet, ist so ein Ziel wegen des Halteproblems unmöglich.
Jump to: