Bitcoin Forum
December 16, 2017, 12:25:27 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Turing-Vollständigkeit  (Read 1216 times)
bill86
Full Member
***
Offline Offline

Activity: 159



View Profile
January 18, 2015, 11: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.

"Prognosen sind äußerst schwierig, vor allem wenn sie die Zukunft betreffen."

-- Kurt Tucholsky (Oder Mark Twain? Oder Winston Churchill? Wer weiß das schon so genau?)
1513383927
Hero Member
*
Offline Offline

Posts: 1513383927

View Profile Personal Message (Offline)

Ignore
1513383927
Reply with quote  #2

1513383927
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513383927
Hero Member
*
Offline Offline

Posts: 1513383927

View Profile Personal Message (Offline)

Ignore
1513383927
Reply with quote  #2

1513383927
Report to moderator
dewdeded
Legendary
*
Offline Offline

Activity: 1050


Monero Evangelist


View Profile WWW
January 18, 2015, 11:16:03 AM
 #2

Das führt dich jetzt zu welcher Frage?
bill86
Full Member
***
Offline Offline

Activity: 159



View Profile
January 18, 2015, 11: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.

"Prognosen sind äußerst schwierig, vor allem wenn sie die Zukunft betreffen."

-- Kurt Tucholsky (Oder Mark Twain? Oder Winston Churchill? Wer weiß das schon so genau?)
lame.duck
Legendary
*
Offline Offline

Activity: 1268


View Profile
January 18, 2015, 11: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.

Gyrsur
Legendary
*
Offline Offline

Activity: 1834


#BEL+++


View Profile WWW
January 18, 2015, 11: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.
IIOII
Legendary
*
Offline Offline

Activity: 1101



View Profile WWW
January 18, 2015, 07: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.

dewdeded
Legendary
*
Offline Offline

Activity: 1050


Monero Evangelist


View Profile WWW
January 18, 2015, 07: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.)

dewdeded
Legendary
*
Offline Offline

Activity: 1050


Monero Evangelist


View Profile WWW
January 18, 2015, 08:39:03 PM
 #8

Why blockchains might want to consider using AT "Turing complete" txs?
https://bitcointalk.org/index.php?topic=822100.0
Gyrsur
Legendary
*
Offline Offline

Activity: 1834


#BEL+++


View Profile WWW
January 18, 2015, 08:51:39 PM
 #9

Why blockchains might want to consider using AT "Turing complete" txs?
https://bitcointalk.org/index.php?topic=822100.0

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
bill86
Full Member
***
Offline Offline

Activity: 159



View Profile
January 19, 2015, 01:15:48 PM
 #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.

"Prognosen sind äußerst schwierig, vor allem wenn sie die Zukunft betreffen."

-- Kurt Tucholsky (Oder Mark Twain? Oder Winston Churchill? Wer weiß das schon so genau?)
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!