archivierte Beiträge lesen
- (SONSTIGES) Was heißt Turingvollständigkeit von Ferby, 08. 09. 2004, 16:01
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 16:01 Uhr von Ferby veröffentlicht.
Hallo,
Ich habe im Internet ein wenig herumgestöbert weil ich wissen wollte was eine programmiersprache ist und was nicht da ich dachte das logo keine programmiersprache ist.
Dabei bin ich immer wieder auf den Begriff: Turingvollständigkeit
gestossen, leider konnte ich über google keine Seite finden die mir diesen Begriff erklären konnte.
Könnt ihr mir eine Seite sagen oder mir möglichst einfach den Begriff Turingvollständigkeit erklären?
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 16:16 Uhr von Yeti veröffentlicht.
Hi,
dazu müsstest du eigentlich ein paar Semester theoretische Informatik belegen... ich versuch's trotzdem.
Eine Turingmaschine ist eine (fiktive) Rechenmaschine, die durch Zustände und Zustandsübergänge definiert ist.
Ein Programm ist dann turingberechenbar, wenn die Turingmaschine dieses in polynomieller Zeit (zur Länge der Eingabe) berechnen kann.
Also schnell. Im Gegenteil zu exponentieller Zeit (y^x), wo die Laufzeit mit Vergrößerung der Eingabe um 1 sich ver-y-facht.
Alaska? :-)
Der Yeti
--
Habe nun, ach! WInfo, BWL, und Mathe, Und leider auch Info!
Durchaus studiert, mit heißem Bemühn. Da steh' ich nun, ich armer Thor!
Und bin so klug als wie zuvor!
sh:( fo:| ch:? rl:? br: n4:& ie:( mo:| va:| de:[ zu:) fl:| ss:) ls:< js:|
http://community.de.selfhtml.org/fanprojekte/selfcode.htm
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 16:35 Uhr von Henryk Plötz veröffentlicht.
Moin,
> dazu müsstest du eigentlich ein paar Semester theoretische Informatik belegen... ich versuch's trotzdem.
Ein halbes Semester reicht. Alternativ ein bisschen in Wikipedia stöbern: http://de.wikipedia.org/wiki/Turingmaschine.
> Eine Turingmaschine ist eine (fiktive) Rechenmaschine, die durch Zustände und Zustandsübergänge definiert ist.
> Ein Programm ist dann turingberechenbar, wenn die Turingmaschine dieses in polynomieller Zeit (zur Länge der Eingabe) berechnen kann.
Nein, eine Funktion ist turing-berechenbar, wenn (big surprise) es eine Turingmaschine gibt die diese Funktion berechnet. Mit der Zeit hat das erstmal gar nichts zu tun. Das was du meinst wären die Probleme die in Polynomialzeit lösbar sind, das ist erstmal uninteressant.
"A ist Turing-vollständig" heisst dann einfach nur dass A genauso mächtig ist wie eine universelle Turing-Maschine, man also in A eine universelle Turing-Maschine emulieren kann (und umgekehrt).
Da eine Turing-Maschine eine bestimmte Klasse von Berechnungsproblemen lösen kann (von der man annimmt dass sie alle Probleme umfasst die "intuitiv anschaulich berechenbar" sind), kann man dann auch mit A alle berechenbaren Probleme lösen.
--
Henryk Plötz
Grüße aus Berlin
~~~~~~~~ Un-CDs, nein danke! http://www.heise.de/ct/cd-register/ ~~~~~~~~
~~ Help Microsoft fight software piracy: Give Linux to a friend today! ~~
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 16:42 Uhr von Yeti veröffentlicht.
Hi,
> Ein halbes Semester reicht. Alternativ ein bisschen in Wikipedia stöbern: http://de.wikipedia.org/wiki/Turingmaschine.
Bei mir kam's erst nach im zweiten.
> Nein, eine Funktion ist turing-berechenbar, wenn (big surprise) es eine Turingmaschine gibt die diese Funktion berechnet. Mit der Zeit hat das erstmal gar nichts zu tun. Das was du meinst wären die Probleme die in Polynomialzeit lösbar sind, das ist erstmal uninteressant.
Richtig. Ich hab's doch glatt wieder mit der NP-Vollständigkeit durcheinander geschmissen. Braucht eh kein Mensch.
Der Yeti
--
Habe nun, ach! WInfo, BWL, und Mathe, Und leider auch Info!
Durchaus studiert, mit heißem Bemühn. Da steh' ich nun, ich armer Thor!
Und bin so klug als wie zuvor!
sh:( fo:| ch:? rl:? br: n4:& ie:( mo:| va:| de:[ zu:) fl:| ss:) ls:< js:|
http://community.de.selfhtml.org/fanprojekte/selfcode.htm
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 16:58 Uhr von Gunnar Bittersmann veröffentlicht.
> Ich hab's doch glatt wieder mit der NP-Vollständigkeit durcheinander geschmissen. Braucht eh kein Mensch.
Doch, damit kannste berühmt werden. Wennde heut Nachmittag noch nichts vorhast, lös doch mal schnell das P=NP-Problem. ;-)
Gunnar
--
"(Der Student) kann sich so völlig dem hingeben, was er naiv für die Computerwissenschaft hält, also der bloßen Verfeinerung seiner Programmiertechniken, daß er sich auf diese Weise effektiv daran hindert, etwas wirklich Wesentliches zu studieren."
(Joseph Weizenbaum in "Die Macht der Computer und die Ohnmacht der Vernunft")
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 18:57 Uhr von Daniel Thoma veröffentlicht.
Hallo Ferby,
da es bisher noch niemand getan hat, erst mal eine Beschreibung einer Turingmaschine
Eine Turingmaschine besteht aus einem unendlich langen Speicherband, mit einem Lese/Schreibkopf, das Anfangs mit Leerzeichen beschrieben ist, einem Startzustand, einer Zustandübergangsfunktion sowie einer Menge zulässiger Bandzeichen und Zustände.
Die Maschine liest nun immer das Zeichen, über dem der Lese/Schreibkopf steht und guckt in einer Tabelle (Zustandsübergangsfunktion) unter dem aktuellen Zustand und dem gelesenen Zeichen nacht, was der nächste Zustand ist, welches Zeichen auf das Band geschreiben wird, ob der Kopf
nach links oder rechts bewegt wird und ob die Rechnung beendet ist.
Die Eingabe wird anfangs auf das Band geschrieben, die Ausgabe steht hinterher auf dem Band.
Eine Sprache ist Turingvollstängig gdw man mit ihr ein Programm schreiben kann, dass eine beliebige Turingmaschine einliest und ausführt
Ich bin mir nicht sicher, ob sie auch von einer Turingmaschine interpretiert werden können muss. Da man aber annimmt, dass es keine Algorithmusdefinition gibt, die mächtiger ist, als die Turingmaschine, ist das nicht so entscheidend.
Grüße
Daniel
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 22:59 Uhr von Gunnar Bittersmann veröffentlicht.
> Eine Turingmaschine besteht aus einem unendlich langen Speicherband ..., das Anfangs mit Leerzeichen beschrieben ist...
> Die Maschine liest nun immer das Zeichen, über dem der Lese/Schreibkopf steht...
Daniel,
Was soll sie da lesen, wenn anfangs nur Leerzeichen auf dem Band stehen?
Das Band ist am Anfang mit Daten beschrieben (die evtl. auch als Programm interpretiert werden).
Gunnar
--
"(Der Student) kann sich so völlig dem hingeben, was er naiv für die Computerwissenschaft hält, also der bloßen Verfeinerung seiner Programmiertechniken, daß er sich auf diese Weise effektiv daran hindert, etwas wirklich Wesentliches zu studieren."
(Joseph Weizenbaum in "Die Macht der Computer und die Ohnmacht der Vernunft")
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 08. 09. 2004, 23:30 Uhr von Henryk Plötz veröffentlicht.
Moin,
> Was soll sie da lesen, wenn anfangs nur Leerzeichen auf dem Band stehen?
>
> Das Band ist am Anfang mit Daten beschrieben (die evtl. auch als Programm interpretiert werden).
"Kommt drauf an"[tm]. Es gibt in dieser Hinsicht keine Beschränkung. Wenn es um Berechenbarkeit geht, nimmt man zwar üblicherweise ein bestimmtes Format (Systemprogrammierer würden jetzt "calling convention" sagen), aber vorgeschrieben ist das nicht.
Ein beliebtes Problem sind zum Beispiel "Fleißige Biber" (engl. busy beaver), also Programme die auf einem leeren Band starten und möglichst viel draufschreiben.
--
Henryk Plötz
Grüße aus Berlin
~~~~~~~~ Un-CDs, nein danke! http://www.heise.de/ct/cd-register/ ~~~~~~~~
~~ Help Microsoft fight software piracy: Give Linux to a friend today! ~~
Was heißt Turingvollständigkeit
Der folgende Beitrag wurde am 09. 09. 2004, 11:44 Uhr von Daniel Thoma veröffentlicht.
Hallo Gunnar,
> Das Band ist am Anfang mit Daten beschrieben (die evtl. auch als Programm interpretiert werden).
Weiter unten habe ich das auch geschrieben. Den Satz am Anfang hätte ich zugegebenermaßen noch einmal umformulieren sollen. Ich wollte sagen, dass auf dem Band überall Leerzeichen stehen außer natürlich an der Stelle, an der die Eingabe steht.
Grüße
Daniel
© 1998-2013 SELFHTMLImpressumSoftware: Classic Forum 3.4
