Diskussion:Turingmaschine/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Turingmaschine/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung auVorlage:SSerhalb der Wikipedia

https://de.wikiup.org/wiki/Diskussion:Turingmaschine/Archiv/1#Thema_1

Brainfuck

Brainfuck ist zwar kein netter Name, aber aktuell ist es eine sehr gute möglichkeit selbst einmal eine Turingmaschine auszuprobieren bzw. zu programmieren. Ich denke das muss unbedingt in den artikel aufgenommen werden, bzw. verlinkt werden.

Es gibt zig solcher Tools, sicher auch mit etwas weniger anstössigen Namen. Du solltest dein Anliegen daher schon Begründen. --matrixx 16:32, 17. Mär 2006 (CET)

Wo denn? Unter "esotherische Programmiersprachen" werden ein paar ähnliche Sprachen genannt - die sind aber von Brainfuck abgeleitet. --213.221.250.85 14:45, 7. Dez. 2010 (CET)

Der Fehler im Artikel Turingmaschine muss raus!

---

Hier möchte ich darauf hinweisen, dass es einen schwerwiegenden Fehler in diesem Artikel gibt!

Implizit wird erklärt, dass eine TM nur dann nicht terminiert, wenn sie in eine Endlosschleife gerät. Das ist schlichtweg falsch.

Meine Verbesserung wurde von Squizzz rückgängig gemacht. Er hat meinen Kommentar noch nicht beantwortet.

Sicher sind alle der Ansicht, dass wir auf alle Fälle Wahrheiten verbreiten sollten. Ich bitte um Vorschläge, wie das zu erreichen ist.

Viele Grüße

--Gerhard Buntrock 03:22, 12. Sep 2005 (CEST)

Und ich möchte darauf hinweisen, dass dies kein schwerwiegender Fehler ist, bevor dies noch korrigiert wird. Es gibt nur 3 Möglichkeiten, wie eine TM auf eine Eingabe reagieren kann:

1. Akzeptieren

2. Verwerfen

3. Loop (oder eben Endlosschleife)

Bei Fall 1 und 2 terminiert sie (terminieren = Ablauf wird beendet) im 3. Fall läuft sie unendlich weiter. Dabei kann es natürlich sein, dass es nie zwei gleiche Konfigurationen oder Konfigurationsfolgen gibt. Ein Enumerator könnte das Speicherband mit unendlich vielen 1sen voll schreiben. Dabei ist nie eine Konfiguration gleich, jedoch ist die Anzahl der Zustände begrenzt. Somit kann man m.E. guten Gewissens von einer Endlosschleife sprechen. Somit gilt: Eine TM terminiert genau dann wenn sie nicht in eine Endlosschleife gerät.

Gruß,

--FG 12:37, 12. Sep 2008 (CEST)

---

in beide Richtungen unsichtbares Band

Müsste es nicht heissen:

in mindestens eine Richtung unendliches Band

Normalerweise startet eine Turingmaschine an der linken festen Seite eines unendlich langen Bandes, ja. --avatar

'Normalerweise' 'links' - nie im Leben! Es gibt viele Konventionen fuer Turing-Maschinen, und eine ist eben das (nur) einseitig unendliche Band. Aber das ist deswegen nicht in irgendeine bestimmte Richtung (nur) einseitig unendlich. Und was meinst Du mit der 'festen Seite'? Die Seite, nach der hin das Band nicht unendlich ist? Eine TM startet auf dem Feld (und in dem Zustand), das (den) ihr die Umgebung zuweist. Die Umgebung kann z.B. eine uebergeordnete TM sein. Bei einer TM mit einem nach beiden Seiten unendlichen Band kann das Startfeld z.B. dasjenige sein mit dem ersten nichtleeren Feld, und das koennte das erste von links sein, aber eben auch von rechts, je nach gewaehlter Konvention. (Uebrigens soll Turing ziemlich Links-Rechts-Schwaechen gehabt haben. Hat manchmal ganze Vortraege in Spiegelschrift an die Tafel gechrieben, bis ihn jemand darauf hinwies.) Ist das Band nur in eine Richtung unendlich, kann man als Konvention festlegen, dass - falls es nach rechts unendlich ist - das Startfeld das erste nichtleere Feld einer Zeichenkette ist, und zwar links, und das dieses stets mit dem ersten (von links aus gesehen) Feld des Bandes ueberhaupt zusammenfaellt. Das komplexere Problem in diesem Zusammenhang ist die Verwendung von 'unendlich'. Meint man 'aktual unendlich' oder 'potentiell unendlich'? - Natuerlich letzteres. Aber richtig richtig ist 'beliebig lang' - immer, wenn es der Rechenprozess erfordert, stiftet die Umgebung ein weiteres Feld. -- Manuel Bonik

---

Es macht übrigens keinen Unterschied, ob eine Turing-Maschine eine oder mehrere Bänder verwendet. Ist das sicher? Ich habe gehört, es gebe Funktionen, die könnten mit zwei Bändern, aber nicht mit einem berechnet werden... -- Fgb

Aus dem hohlen Bauch heraus sage ich jetzt mal, dass es solche Funktionen nicht geben kann. Die Bänder sind abzählbar unendlich, d.h. es gibt eine Bijektion zwischen ihnen, und die muss die Turing-Maschine ausführen können. D.h. also, die T.M. kann mit einem Band zwei Bänder "emulieren". Der Rechenaufwand mag dabei steigen, aber letztendlich bleibt er von gleicher Ordnung, lediglich die Konstante ändert sich. -- Flups

Es gibt beliebige Speicher (im allgemeinen ein beliebiger Graph), also nicht nur Bänder. Die können alle die gleichen Funktionen berechnen, aber mit unterschiedlicher Effizienz. --Vulture

Turingmaschinen mit mehreren Bändern haben definitiv nicht mehr Rechenpower als Turingmaschinen mit einem Band!

---

Wie schreibt man denn Turingmaschine jetzt? Turing-Maschine oder Turingmaschine? Google spuckt ca. 12200 Ergebnisse für "Turing-Maschine" und ca. 12300 für "Turingmaschine" aus, ist also auch nicht sehr aussagekräftig ... :)

Ich hab auf jeden Fall die Schreibweise im Artikel dem Titel angepasst ... --brunft 10:54, 12. Mär 2004 (CET)

-- Nach den neuen Regeln der Rechtschreibreform sind beide Schreibweisen möglich. Siehe http://www.ids-mannheim.de/reform/c3.html

§ 51: Man kann einen Bindestrich in Zusammensetzungen setzen, die als ersten Bestandteil einen Eigennamen haben, der besonders hervorgehoben werden soll, oder wenn der zweite Bestandteil bereits eine Zusammensetzung ist.

Hutschi

---

Eine Maschine mit zwei nichtgetakteten Bändern, könnte die mächtiger sein, als eine Turingmaschine? Hier spielte ja dann der Zufall eine Rolle. (Ich nenne sie nicht "Turingmaschine", denn es ist ja keine.)

Wenn eine Fliege da wäre, die sich auf das Band setzt und dafür sorgt, dass ein Zeichen nicht erkennbar wird, wäre die Maschine mächtiger, als die entsprechende Turingmaschine?

(Es wäre eine Turingmaschine, die irren kann.)

-- Hutschi 13:42, 16. Mär 2004 (CET)

Wenn man Zufallsfaktoren ins Spiel bringt, werden die Ergebnisse sicherlich mannigfaltiger. Aber das entspraeche nicht der Definition von TMn als deterministischen Maschinen. Turing sieht immerhin auch eine Zufallsmaschine vor, mit dem schoenen Namen 'Orakel'. Nicht-deterministische TMn sind als solche definiert, die jeweils die Wahl zwischen mehreren Folge-Zustaenden haben. Aber die koennen auch nicht mehr als determistische TMn. Vgl. unten. - Manuel Bonik

---

"Turing zeigte, dass diese Maschine jedes algorithmisierbare (berechenbare) Problem lösen kann."

Das verstehe ich so, dass Turing die Churchsche These zumindest in eine Richtung bewiesen hat. Laut dem entsprechenden Artikel ist diese These aber unbeweisbar. Missverstehe ich den Artikel, ist die andere Richtung schwieriger oder liegt hier ein Fehler vor?

-- Boogieman

Der Satz ist meiner Meinung nach zwar nicht falsch, aber sinnlos - wenn mit "berechenbar" Turing-berechenbar gemeint ist. Turing gab ja mit diesem Modell erst eine Definition von "Berechenbarkeit" an, die mit anderen Modellen nachweislich dieselbe Klasse von Funktionen beschreibt. Die Churche These ist und bleibt unbeweisbar. Ich habe den Satz erst einmal entfernt. --zap 14:30, 28. Jun 2004 (CEST)

---

Ganz allgemein bin ich mit dieser Seite der Wikipedia unzufrieden. Die Seite erklärt zwar, was eine Turingmaschine ist, erhellt dieses aber nur für Mathematiker. Es fehlt eine allgemein verständliche Erklärung und Einführung. So wie die Seite hier steht, ist sie nur für Mathematiker und Informatiker von Interesse, aber für diese Zielgruppe ist die Wikipedia eigentlich nicht da.

--Henrik Fisch 13:56, 19. Apr 2004 (CEST)

Außerdem wird nicht erklärt, was es mit dem ominösen Nichtdeterministisch auf sich hat. -- Nichtich

Nichtdeterministisch im Gegensatz zu deterministisch bedeutet im Falle der Turingmaschine, das das Programm der Turingmaschine in einer besonderen Konfiguration (gemeint ist; mit einem bestimmten gelesenen Zeichen und einem bestimmten Zustand - also die Linke Seite der Programmvorschrift) mehrere Folgekonfigurationen enthält, von denen nur eine ausgewählt wird. Die deterministische TM kennt nur einen Folgezustand.

lies doch mal Nichtdeterminismus ;-) Pinguin.tk 14:14, 7. Jul 2004 (CEST)

---

Die Turingmaschine [..] wurde zur Lösung des von Kurt Gödel formulierten Vollständigkeitsproblems erdacht.

Gödel bewies seinen Unvollständigkeitssatz 1930. Turing hat seine Arbeit aber erst 1937 veröffentlicht ("On computable numbers, with an application to the Entscheidungsproblem"). Weiß jemand mehr über den Zusammenhang von Unvollständigkeitssatz und Turingmaschine? --zap 13:03, 16. Jul 2004 (CEST)

Die TM wurde zur Lösung des Entscheidungsproblems erdacht, wie der Titel von Turings Aufsatz ja schon sagt. Wer das Entscheidungsproblem genau gemacht hat, weiss ich nicht. Aber Turing reagierte auf das sogenannte Hilbertsche Programm vom Mathematikerkongress 1900 in Paris. -- Manuel Bonik

Ich sehe gerade das es ja um den Vollständigkeitssatz geht (nicht Unvollständigkeit), was die Sache aber nicht besser macht - Gödel hat auch den Vollständigkeitssatz lange vor Turing's Publikation bewiesen (nämlich 1929 - siehe engl. Wikipedia en:Gödel's_completeness_theorem). Ich schätze der o.g. Satz ist einfach falsch. --zap 12:53, 31. Aug 2004 (CEST)

fleißiger Biber

Die Aussage, dass man fleißiger Biber nicht mit Zahlen über 4 berechnen kann, ist falsch, in dem Artikel über fleißiger Biber sind z.b. höhere Zahlen angeführt, es wurde aber zumindest bis 12 berechnet.

Der Satz lautete: Für 1 bis 4 Zustände konnte das Problem berechnet werden, aber bereits für "nur" 5 Zustände ist der "beste" Fleißige Biber noch nicht bekannt. Das ist nach meinem Wissen korrekt. Der derzeit fleißigste Biber mit 5 Zuständen produziert 4098 Einsen. Ob es aber der beste ist, ist nicht bekannt.--zap 14:45, 14. Dez 2004 (CET)

Was heißt schreiben ?

Eine der 3 grundlegenden Funktionen der Turingmaschine ist das Schreiben. Wird dabei der vorhandene Eintrag auf dem Band überschrieben ? Oder wird eingefügt ? Links oder rechts eingefügt ?

Schreiben heisst überschreiben: das zuletzt gelesene Zeichen wird immer ersetzt (möglicherweise wieder durch das selbe Zeichen). -- D. Dÿsentrieb ⇌ 16:13, 13. Aug 2005 (CEST)

Gibt es gute didaktische Beispiele einer Turingmaschine in verschiedenen Programmiersprachen ?

Turingmaschinen eignen sich kaum für "reale" Programme, Implementationen von Turingmaschinen in höheren Programmiersprachen sind selten elegant. Es gibt aber reichlich visuelle Turingmaschinen-Simulatoren, google einfach mal: [1] oder [2]. Ich fand das hier ganz anschaulich [3], aber das Ding kann nur ein Programm. Flexibler aber nicht so hübsch ist diese Variante [4].

Hier ist noch eine TM, implementiert in Java [5] - hab' ich aber nicht ausprobiert. HTH -- D. Dÿsentrieb ⇌ 16:13, 13. Aug 2005 (CEST)

Endlosschleife

Es wurde die Behauptung aufgestellt, dass eine Turingmaschine auch nie halten kann ohne in eine Endlosschleife zu gehen. Das ist meines Erachtens falsch. Das die Zustandsmenge und das Bandalphabet endlich sind, sind auch die Definitionsmenge $Q\times \Gamma$ und die Bildmenge $Q\times \Gamma \times \{L,0,R\}$ der Übergangsfunktion endlich. Damit muss die Turingmaschine, wenn sie nicht hält, irgendwann wieder auf ein Tupel aus $Q\times \Gamma$ stoßen bei dem sie schon einmal war und gerät dann in eine Endlosschleife. --Squizzz 15:32, 9. Sep 2005 (CEST)

Du vergisst den Bandinhalt. Weiterhin müssen wir uns über den Begriff der Schleife einigen. Eine Schleife ist sicher dann gegeben, wenn alles, Bandinhalt, Position und Zustand sich wiederholen. Abstraktere Schleifen entstehen, wenn die Maschine z.B. immer eine 1 schreibt und nach rechts geht. Noch abstrakter wird es, wenn sie einmal ganz nach rechts geht, eine 1 schreibt und dann ganz nach links geht und eine 1 schreibt und jetzt wieder nach rechts, ...; offenbar ist jetzt der Schleifendurchgang nicht mal mehr immer gleich lang! Es wird offensichtlich, dass die Maschinen noch viel kompliziertere Schleifen durchlaufen können. Irgendwann kann ich das nicht mehr als Schleife akzeptieren. Denn genau die, die wir nicht mehr verstehen, machen das Halteproblem unentscheidbar. Hier sind Rechenwege drin, die wir rekursiv nicht entscheiden können, prinzipiell nicht! Wenn alles Schleifen wären, könnten wir das Halteproblem entscheiden! Denn jede Schleife, egal wie wir sie definieren --- ich denke, hier sind wir uns bestimmt einig --- ist eine entscheidbare Eigenschaft. Daher dürfen wir nicht sagen, dass der einzige Grund des Nichthaltens eine Endlosschleife sein kann. Das ist definitiv falsch. Daher konnte ich mich nicht beherrschen und habe meinen Beitrag eingefügt. ;-)

Viele Grüße --Gerhard Buntrock 16:51, 9. Sep 2005 (CEST)

Warum sollte es keine Schleife mehr sein, nur weil sich ihre Länge verändert? siehe http://de.wikipedia.org/wiki/Schleife_(Programmierung) "Eine Schleife ist eine Kontrollstruktur in Programmiersprachen. Sie wiederholt einen Anweisungs-Block – den so genannten Schleifenrumpf oder Schleifenkörper – so lange, wie eine Laufbedingung gültig ist oder bis eine Abbruchbedingung eintritt. Schleifen, deren Laufbedingung immer erfüllt ist oder die ihre Abbruchbedingung niemals erreichen, und Schleifen, die keine Abbruchbedingungen haben, sind Endlosschleifen." Nur weil du etwas nicht verstehen/entscheiden kannst, ist es nicht unverständlich/unentscheidbar. --213.221.250.85 14:57, 7. Dez. 2010 (CET)

Ab dem Satz „Denn genau die, die wir nicht mehr verstehen, machen das Halteproblem unentscheidbar.“ kann ich dir nicht mehr folgen. Insbesondere ist mir unklar, warum die Terminierung einer Schleife entscheidbar ist: das Halteproblem selbst benutzt eine While-Schleife. Nichtsdestotrotz habe ich den letzten Hinweis auf die Endlosschleife gelöscht, der noch übrig war. Noch eine Bitte: schreibe doch hier in er Diskussion linear und ohne Einrückungen und übermäßigen Gebrauch von Trennlinien. --Squizzz 08:15, 12. Sep 2005 (CEST)

Luecke in der Schlussfolgerung

Im Aritkel steht: So kann etwa an Hand des Halteproblems gezeigt werden, dass es mathematische Funktionen gibt, die nicht von Menschen (und folglich auch nicht von einer Turingmaschine) berechnet werden können.)

Dort wird also behauptet, dass eine Turingmaschine etwas nicht berechnen kann, was auch ein Mensch nicht berechnen kann. Aber wo wird bewiesen, dass eine Turingmaschine auf das beschraenkt ist, was ein Mensch kann? Bisher ist doch erst die eine Richtung bewiesen, dass sie mindestens die Maechtigkeit eines Menschen hat.

-- Gruss sparti 13:59, 12. Nov 2005 (CET)

Behauptet das aber nicht gerade die (nicht bewiesene, jedoch allgemein als korrekt angenommene) Church-Turing-These? Stern !? 14:05, 12. Nov 2005 (CET)

Doch das stimmt. Man koennte es hier aber nochmal erwaehnen. Trotzdem Danke. -- sparti 19:17, 12. Nov 2005 (CET)

Es wurde nirgendwo bewiesen, dass eine Turingmaschine mindestens so mächtig wie ein Mensch ist. Denn das ist genauso unbeweisbar wie die Churche These!

Kleine Änderungen an der Formalen Definition

In disem Artikel stand in der Formalen Definiton das: $\Sigma \subset \Gamma$ das endliche Eingabealphabet sei, dieses halte ich für falsch, geanuso wie: $\square \in \Gamma \setminus \Sigma$ steht für das leere Feld. Ich meine dieses ist falsch, da die Turingmaschien auch das leere Feld schreiben können muss, sonst würde es nicht möglich sein, wenn ein Zeichen in einem Feld steht, dieses durch das leere Feld zu ersetzen, da die Turingmaschine dieses nicht schreiben könnte. Daher meine ich, muss die erste Definition $\Sigma \subseteq \Gamma$ das endliche Eingabealphabet heißen (allso das leere Feld mit einbeziehen). Daraus folgt dann, dass die zweite Definiton nicht möglich ist, da $\Gamma$ dann gleich $\Sigma$ ist und das leere Feld dann nicht mehr definiert wäre.

Aus diesm Grund, musste dann auch das Beispiel geändert werden und zwar muss in die Menge $\Sigma$ auch noch das leere Feld aufgenommen werden, dieses ist auch logisch, denn wenn die Maschine kein leeres Feld schreiben könnte, könnte es aus einer 1 auf dem Band kein leeres Feld machen, dass dieses aber nötig ist, sieht man an dem Beispiel.

Daher habe ich diese beiden Punkte in dem Artikel verändert. Falls einer begründet anderer Meinung ist kann er es ja wieder ändern.

MfG
Ulf Buse (geschrieben: 1.12.2005)

Hallo Ulf, ich bin tatsächlich anderer Meinung: In allen Definition von Turingmaschinen, die ich kenne, ist $\square \not \in \Sigma$. Das hat auch einen guten Grund: $\Sigma$ ist das Eingabealphabet, und $\square$ ist kein Zeichen der Eingabe. Das würde auch zu Verwicklungen führen, da das Eingabewort ja zu Beginn auf dem Eingabeband steht, das sonst mit $\square$ gefüllt ist. Wenn jetzt $\square$ Teil des Eingabealphabets ist, dann ist ja gar nicht klar, was jetzt das Eingabewort ist, etwa "Wort" oder "$\square \dots \square$Wort$\square \dots \square$"...? Natürlich soll die Turingmaschine Zeichen löschen können, dafür muss aber $\square$ nicht Teil des Eingabe- sondern nur des Bandalphabets sein. Das ist ja aber durch $\square \in \Gamma \setminus \Sigma$ gesagt.

Also, ich habe den Artikel dementsprechend (zurück) geändert.

Gruß --eo !? 23:10, 1. Dez 2005 (CET)

Laut Introduction to the Theorie of Computation von Michael Seipser ist das Blank-Symbol definitiv nicht im Eingabesymbolvorrat enthalten. Das sollte soweit korrekt sein, da dieses Symbol eben ein Zeichen ist, welches nur auf dem Band erlaubt ist und eben als Markierung für freie Zellen gedacht ist. Jedoch ist das Blank-Symbol laut Seipser nicht bestandteil des 7-Tupels der Turing-Maschine sondern statt dessen die Reject-Zustände. Dieses sollte m.E. statt dessen eher angepasst werden. Die Definition lautet wie folgt:

A Turing machine is a 7-tuple, $(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{a}ccept,q_{r}eject)$, where $Q,\Sigma ,\Gamma$ are all final sets and

• $Q$ is a set of states,
• $\Sigma$ is the input alphabet not containing the blank symbol $\square$
• $\Gamma$ is the tape alphabet, where $\square \in \Gamma$ and $\Gamma \supset \Sigma$,
• $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ is the transition function,
• $q_{0}\in Q$ is the start state
• $q_{accept}\ inQ$ is the accept state, and
• $q_{reject}\in Q$ is the reject state, where $q_{accept}\not =q_{reject}$

[S. 142, Introduction To The Theorie Of Computation, Michael Seipser, Thomson] Wie gesagt. Das Blank gehört nicht in das Eingabealphabet, da es ein Bandsymbol ist und eben nur eine leere Stelle auf dem Band markiert. Dennoch scheint es auch andere Definitionen einer Turing-Maschine zu geben. Es ist die Frage, welche nun die richtigere ist. Auf jeden Fall ermöglicht die vorhandene Definition nicht das explizite Zurückweisen einer Eingabe. Dies ist zwar bei Kellerautomaten und nichtdeterministischen endlichen Automaten auch der Fall, kenne ich aber eben bei Turing-Maschinen anders.

MfG FG

Animation

TM Animation

Ich habe vorhin eine Animation einer Turingmaschine erstellt. Sie arbeitet nach den Regeln die hier im Beispiel angegeben werden. Da ich bisher noch nie bei wikipedia was reingestellt habe, traue ich mich nicht einfach den Artikel zu ändern. Vielleicht macht das jemand von euch besser. Das Bild habe ich schon hochgeladen. http://de.wikipedia.org/wiki/Bild:Turing.gif Die Autoren des Programms JFLAP (welches sich übrigens hervorragend für Turingmaschinen- und Automatensimulation eignet) aus dem ich die Screenshots entnommen habe wünschen jedoch eine Verlinkung mit der Animation.

Würde mich freuen wenn mein erster kleiner Beitrag veröffentlicht würde.

Erstmal vielen Dank für den Beitrag, eine Animation könnte sehr helfen, den Artikel anschaulicher zu machen. Nun zur Kritik:

• Das Band ist sehr klein in der Ecke - und dabei ist es doch eigentlich die Hauptsache. Wenn man das Bild auf eine Grösse reduziert, in dem es im Artikle brauchbar wäre (siehe rechts), ist das Band kaum noch zu erkennen. Man sieht auf den ersten Blick nur den Endlichen Automaten, und zu dem müsste man noch den Zusammenhang erklären.
• Die Animation sollte "geloopt" sein, d.h. die Berechnung sollte nach einer kurzen Pause erneut beginnen. Sonst muss man die Seite neu laden, um das nochmal zu sehen, und das ist nervig (und kommt auch nicht jeder drauf).
• Auf der Bildbeschreibungsseite sollte noch stehen, was denn diese TM berechnet, und wie (Pseudocode?). Das sollte dann auch in der Bildunterschrift erscheinen.
• Man sieht recht deutlich, dass das mit screenshots "abgefilmt" ist - mir ist klar dass das bearbeiten einer Animation fummelig ist, aber vielleicht hilft ja jemand, der sich damit auskennt.
• Allgemeint gibt es oft Probleme, animationen zu skalieren - in diesem Fall funktioniert es anscheinend aber. Für Animationen bietet es sich (anders als bei "normalen" Bildern) an, eine massgeschneiderte, kleine Version (evtl zusätzlich) hochzuladen.
• Dass du die Entwickler des Programms um Erlaubnis gefragt hast, ist geradzu vorbildlich. Ich denke nicht, dass das nichtmal nötig war: ich sehe keine Elemente der GUI, die ausreichend Schöpfungshöhe hätten, als dass es den Programmierern Rechte an dem Screenshot geben würde.

Ich hoffe, ich hab dich jetzt nicht abgeschreckt - wie gesagt, ich fände eine Animation hier prima! Ach ja: wie du das Bild in den Artikel einbinden kannst, siehst du, wenn du die den Wiki-Text dieses Kommentars anschaust. Ich habe den Link zum Bild ganz oben in diesen Abschnitt eingefügt. -- D. Dÿsentrieb ⇌ 01:52, 19. Feb 2006 (CET)

Die Animation habe ich gerade mal neu überarbeitet, und neu hoch geladen. Ich hoffe die Darstellung des Bandes ist jetzt deutlicher. Zwar noch genausogroß (wir wollen ja keine hässlichen Verpixelungen). Sie ist geloopt mit 5 Sekunden Pause. Ich denke durch die jetzige Größe der Animation ist gewährleistet, dass sie auch skaliert noch erkennbar ist. -- Razo 18:26, 19. Feb 2006 (CET)

Ich habe jetzt die Animation mit dem Text des Beispiels verlinkt. Ich hoffe das ist so i.O.

Hi, irgendwie war das Bild noch nicht zu sehen. Ich habe es jetzt mal unter die Tabellen gesetzt. --87.123.38.12 12:17, 20. Feb 2006 (CET)

Noch eine Frage: Jetzt ist es ja so, dass jeder Zustand zwei Bezeichnungen trägt, q_(i-1) und s_i. Da im Beispiel ausschließlich von s_i die Rede ist, wäre es vielleicht ganz schön, wenn statt q_(i-1) dort s_i stehen würde ( 0 < i <= 6 ). Dann könnte man die s_i, die im Augenblick da stehen, wieder rausnehmen.. meinst du das das technisch möglich wäre? --87.123.38.12 12:32, 20. Feb 2006 (CET)

Ich hatte es eigentlich schon so beabsichtigt, dass die Animation nicht direkt in den Artikel eingebunden wurde, sondern nur verlinkt, weil sich das Ding ja die ganze Zeit bewegt. Mich persönlich stört das einwenig in einem Artikeltext.

Ansonsten kann ich mir gerne die nächsten Tage nochmal Zeit nehmen und die Bezeichnungen anpassen. Außerdem dachte ich mir, man könnte das Band über den Automaten setzen, damit es als erstes ins Blickfeld fällt. Razo 15:48, 20. Feb 2006 (CET)

Eine Möglichkeit ist es, den ersten "Frame" der Animation getrennt hochzuladen und im Artikel zu zeigen - im Untertitel könnte dann stehen "Animation ansehen", mit Link auf die Animation. Wie z.B. beim ersten Bild in Julia-Menge -- D. Dÿsentrieb ⇌ 18:37, 20. Feb 2006 (CET)

Mich würde diese Animation schon sehr interesieren. Wo köntne ich sie denn jetzt finden?!

Fehler in der Erläuterung des Beispiels

Im Beispiel der Turingmaschine wird behauptet dass die genannte Turingmaschine mit initial "111" und sonst nur leeren Feldern auf dem band die Anzahl der Einsen verdoppelt (wobei natürlich die 0 in der Mitte stehen bleiben muss). Das ist falsch. Denn diese Maschine benötigt Nullen die sie lesen kann um sie dann zu überschreiben. Also braucht sie als Input z.b "1110000" (darauf folgende Felder sind dann irrelevant). Sprich die Sprache der akzeptierten Wörter wäre L=1^i 0^i+1. (i >= 0)

Null ist das leere Feld und gehört lt. Definition zum Bandalphabet. Die Turingmaschine M aus dem Beispiel kann ein leeres Feld erkennen ('lesen') und je nach Überführungsfunktion weiter verfahren und, wie du sagst, kann sie die leeren Felder (also die Nullen) auch überschreiben. Andererseits gehört die Null aber nicht zum Eingabealphabet; damit wäre es dann falsch zu sagen, die Eingabe müsse 1110000 sein. --87.123.38.12 11:58, 20. Feb 2006 (CET)

Wo wird definiert, dass ein leeres Feld der Null entspricht? Was wäre wenn das Eingabealphabet aus m und n bestünde anstatt aus 0 und 1? Razo 15:52, 20. Feb 2006 (CET)

Oh ich nehme alles zurrück. Siehe Diskussion der Formalen Definition oben. Eingabealphabet ist dann in diesem Fall nur 1 und die 0 entspricht dem leeren Feld. Oder sehe ich da immernoch etwas falsch? Razo

Nein, ich sehe das auch so. Gruss, --87.123.39.78 12:49, 21. Feb 2006 (CET)

Turingmaschine genauso fähig wie der Mensch???

Ich will nicht den Eindruck machen, dass ich mich für intelligenter halte als alle anderen die über das Thema nachgedacht haben und wenn ich mit meiner Behauptung eurer Meinung nach falsch liege so weißt mich doch bitte darauf hin, jedoch ist mir Folgendes aufgefallen:

Am Anfang des Artikels steht, dass die Turingmaschine dieselben (wenn nicht sogar mehr) mathematische Fähigkeiten besitzt wie der Mensch. Desweiteren wird auf das Halteproblem eingegangen, welches von einer Turingmaschine nicht zu lösen ist. Dieses Halteproblem ist uns Menschen jedoch (soweit ich das Problem richtig verstanden habe) allgemein bekannt. Mir fällt dazu ein Beispiel ein bei dem zwei Kinder sich um ein Spielzeug streiten und daran ziehen. Das eine Kind A sagt zu Kind B, dass es erst loslässt wenn Kind B auch loslässt. Da Kind B dies erwidert streiten sie sich eine Zeit lang (bis hierhin wie bei der Turingmaschine). Nach einiger Zeit werden sie jedoch zu einer von (schätzungsweise) zwei möglichen Lösungen kommen:

• Ein Kind wird loslassen und das andere Kind bekommt das Spielzeug
• Beide Kinder einigen sich im selben Moment loszulassen und kein Kind bekommt das Spielzeug

Wie auch immer die Entscheidung ausfällt, beruht sie auf der Erkenntnis, dass die Kinder sich in einer, nicht durch aufeinander folgende Operationen lösbaren, Situation befinden. Die Lösung des Problems beruht also nicht auf dem Besitz des Spielzeugs (bzw. dem Anhalten) an sich, sondern der Erkenntnis, dass man das Spielzeug nicht besitzen kann (bzw. das ein anhalten nicht möglich ist) oder dass eine Lösung nur durch eine zeitgleiche Handlung eintritt. Der Mensch ist in der Lage eine solche Situation zu erkennen und seinen Lösungsbegriff auf das Nichtvorhandensein einer Lösung erweitern (keine Lösung ist auch eine mögliche Lösung des Problems; ähnlich wie eine leere Menge) und daraus die nötigen Schlüsse zu ziehen, sowie Entscheidungen zu treffen. In diesem Gebiet ist der Mensch der Turingmaschine meiner Meinung nach überlegen.

Dein Beispiel beschreibt eher das Deadlock-Problem, weniger das Halteproblem. Ausserdem kannst du eine math. Funktion nicht mit dem Gehirn eines Menschen vergleichen. Ob das menschl. Gehirn mächtiger als eine Turingmaschine ist kann erst beantwortet werden, wenn wir wissen ob das menschl. Gehirn mächtiger als eine Turingmaschine ist ;). (Bis dahin halte ich eine psychologische oder gar philosophische Sicht auf dieses Thema für nicht angebracht) --matrixx 09:29, 28. Jun 2006 (CEST)

Natürlich ist der Mensch (bzw. das menschliche Gehirn) mindestens genauso mächtig wie eine Turingmaschine: jeder Mensch sollte in der Lage sein, eine gegebene Turingmaschine zu simulieren (wenn er belieig viele Bleistifte, Radiergummi und Papier zur Verfügung hat). Damit kann eine Turingmaschine nicht mehr machen als ein Mensch. -- PapaNappa 10:00, 17. Sep. 2011 (CEST)

Warum sollte der Mensch der Turingmaschine bei deinem Beispiel überlegen sein? Du mußt dem entsprechenden Programm ja nur die fehlenden Parameter geben, die bei den Kindern zur Lösung führen. Ich sehe keinen Grund zu der Annahme, dass die Lösung des Problems nicht berechenbar wäre. --213.221.250.85 15:04, 7. Dez. 2010 (CET)

was the fuck ist "turingmächtig"??

Mehrere Artikel verlinken diesen Begriff hierher!!

Im Zusammenhang mit Rechenmaschinen (-modellen etc.) soll es wohl bedeuten, dass die Maschine genau die Funktionen berechnen kann, die auch schon von Turingmaschinen berechnet werden können, d.h. nach der Church-Turing-These alle berechenbaren Funktionen.--89.247.68.10 11:06, 1. Okt. 2007 (CEST)

Vielleicht sollte man dort jeweils auf Turing-Vollständigkeit verlinken? Oder auf die Church-Turing-These? --Wutzofant (✉✍) 15:51, 1. Okt. 2007 (CEST)

Also in dieser[6] Liste habe ich keinen änderungsbedürftigen Link gefunden. Ich hab aber mal Turingmächtigkeit - ursprünglich eine Weiterleitung auf Church-Turing-These - auf Turing-Vollständigkeit weitergeleitet. Gruss, --89.247.108.194 10:53, 2. Okt. 2007 (CEST)

Bild

Nur eine Kleinigkeit: Im zweiten Bild von oben (animiert) wird nach jedem Schritt das Band bewegt (L,R,0) - in der Definition und im Beispiel steht L,R,0 aber für die Kopfbewegung. --89.247.121.228 13:06, 2. Jul. 2007 (CEST)

Ich habe die Animation gemacht. Mit bewegtem Lese-Schreib-Kopf sähe es nicht so schön aus - es wäre wegen der variablen Kopfposition schwerer so sehen. Letztendlich ist die konkrete Umsetzung der TM eine Vereinbarungssache. Die TM in der Animation hat auch keinen Endzustand, sondern stoppt bei Aufruf der letzten Adresse. Wenn du möchtest, kannst du ja eine kurze Erläuterung in die Bildlegende schreiben. Ich denke aber, dass das nur verwirren und vom Thema ablenken würde.--stefan 09:57, 31. Okt. 2007 (CET)

Das war nur eine Inkonsistenz die mir so aufgefallen war. Eine Erläuterung in der Bildlegende würde in der Tat nur verwirren. Das mit dem Endzustand war mir noch gar nicht aufgefallen :-) Gruß, --89.247.72.222 01:27, 27. Nov. 2007 (CET)

Der Gegensatz Sprache und Maschine

Die Sprache ist das Urmedium des Menschen. Neben den natürlichen Sprachen gibt seit vielen Jahren auch formale Sprachen, zu denen das Formelsystem der Mathematik und die vielfältigen Ausdrucksweisen der Naturwissenschaften gehören.

Eine Automat bzw. eine Maschine hingegen ist etwas physisch Vorhandenes bzw. Vorstellbares oder Konstruierbares.

Weil hier von der Vorstellung einer physisch existenten Maschine (sie ist m.E. realisierbar) geredet und gedacht wird, ist die TM kein mathematisches oder sprachliches sondern ein physisches Modell! --Jens611 11:25, 22. Aug. 2007 (CEST)

Verstehe ich das richtig?

"Akzeptiert eine Turingmaschine eine Sprache und hält sie zusätzlich bei allen Eingaben, die nicht zu dieser Sprache gehören, so entscheidet die Turingmaschine diese Sprache."

Akzeptiert eine Turingmaschine eine Sprache und haltet zusätzlich bei allen Eingaben die nicht zu dieser Sprache gehören, dann entscheidet sich die Turingmaschine für diese Sprache. --62.203.137.198 23:18, 30. Sep. 2007 (CEST)

Entscheidbar zu sein, ist zunächst mal eine Eigenschaft die eine formale Sprache haben (oder nicht haben) kann. Eine Sprache ist nun genau dann entscheidbar, wenn es eine Turingmaschine M gibt, die zu jeder Eingabe eines Wortes entscheidet, ob dieses Wort zur Sprache L gehört oder nicht. Dazu muss sie in jedem Fall anhalten, denn würde sie nicht anhalten wäre ja unklar ob das Eingabewort nun zu L gehört oder nicht. D.h. eine Turingmaschine entscheidet sich nicht für eine Sprache L, sondern entscheidet die (Zugehörigkeit von Worten zur) Sprache L. Gruss, --89.247.68.10 10:53, 1. Okt. 2007 (CEST)

Frage zu Ausdruck

Weiss jemand, woher der Ausdruck Turing-Maschine stammt? Hat A. Turing des Ausdruck selbst gebraucht, wenn ja wo? (das müsste doch im Artikel stehen, oder?) Rolf Todesco 19:18, 3. Dez. 2006 (CET) --Rolf Todesco 23:46, 4. Feb. 2009 (CET)

Interessante Frage. Hab dazu das hier gefunden: [7] [8] Danach hat Alonzo Church 1937 (also kurz nach Turings Veröffentlichung) den Ausdruck Turing-Maschine als erster benutzt. Andere Internet-Quellen behaupten aber, Kleene (eine Student von Church) hätte den Begriff eingeführt. [9] Turing selbst benutzte wohl den Begriff computing machine. --89.247.27.93 01:19, 5. Feb. 2009 (CET)

Danke -- Rolf Todesco 10:18, 5. Feb. 2009 (CET)

neuer Weblink

Es wurde ein neuer Weblink auf eine JScript-basierte JScript-basierte Turing-Maschine zugefügt. Hat das Ding jemand zum Laufen gebracht? Dokumentation gibt es jedenfalls anscheinend gar keine, und entweder ich bin der einzige, bei dem das Teil nicht funktioniert, oder der Wert dieses Links ist gleich null... -- Kilessan 09:21, 18. Mai 2009 (CEST)

Ich habe den Link revertiert, die Simulation funktioniert nicht. Doch selbst wenn, sehe ich in dem Link aufgrund der Schnelllebigkeit des Webs keinen Mehrwert für den Artikel.--my 2 ct. 10:55, 18. Mai 2009 (CEST)

Beispiel zu kompliziert

Sorry, aber ich versteh das Beispiel nicht. Außerdem vertehe ich nicht warum es eine Überführungsfunktion gibt und diese überhaupt nicht definiert ist. (nicht signierter Beitrag von 77.189.3.26 (Diskussion | Beiträge) 10:06, 26. Jul 2009 (CEST))

Die erste Tabelle in dem Beispiel ist die Definition der Überführungsfunktion $\delta$. Ich habe im Artikel (Entwurf) dazu einen Satz ergänzt. Vielleicht hilft dir das schon weiter.. Gruß --89.247.41.136 13:07, 26. Jul. 2009 (CEST)

achso... jetzt versteh ichs. danke. (nicht signierter Beitrag von 77.189.2.76 (Diskussion | Beiträge) 13:12, 27. Jul 2009 (CEST))

Überblick über Variationsmöglichkeiten - Variationen gerechtfertigt durch These von Church?

Die Vielfalt ist theoretisch durch die These von Church gerechtfertigt, welche im Hinblick auf die Berechenbarkeit die Äquivalenz aller universellen Maschinenmodelle postuliert.

AFAIK ist die Vielfalt dadurch gerechtfertigt, dass sich die ganzen Modelle gegenseitig simulieren können. Das beweist man normalerweise, bevor man eine neue Version verwendet, indem man zeigt, wie sie eine bekannte universelle Turingmaschine simulieren kann. Oder habe ich da etwas falsch verstanden? -- PaMaRo 17:03, 26. Aug. 2009 (CEST)

Definitionsfragen

• $Q$ ist die endliche Zustandsmenge
• $\Sigma$ ist das endliche Eingabealphabet <-- was vesteht man unter dem Eingabealphabet, und warum ist das Eingabealphabet ein expliziter Bestandteil der Definition?
• $\Gamma \supset \Sigma$ ist das endliche Bandalphabet <-- ist Gamma das endliche Bandalphabet, oder ist Sigma das endliche Bandalphabet? (Nachgefragt, um konsistent mit dem unteren Kommentar zu sein)
• $\delta :(Q\setminus F)\times \Gamma \mapsto Q\times \Gamma \times \{L,0,R\}$ ist die Überführungsfunktion
• $q_{0}\in Q$ ist der Anfangszustand
• $\square \in \Gamma \setminus \Sigma$ steht für das leere Feld (Blank)
• $F\subseteq Q$ ist die Menge der End- bzw. akzeptierenden Zustände <-- Ist F die Menge der Endzustände und Q ist die Menge der akzeptierenden Zustände? Wäre es nicht besser, diesen Satz anders zu formulieren: F ist die Menge der Endzustände, Q ist die Menge der akzeptierenden Zustände. Es gilt $F\subseteq Q$.......?

Außerdem

Akzeptiert eine Turingmaschine eine Sprache und hält sie zusätzlich bei allen Eingaben, die nicht zu dieser Sprache gehören, so entscheidet die Turingmaschine diese Sprache.

Was heißt es eigentlich, wenn eine Turingmaschine hält? Hält eine Turingmaschine genau dann, wenn sie einen Endzustand erreicht hat? Oder hält eine Turingmaschine genau dann, wenn die Turingmaschine einen Zustand und eine Kopfposition erreicht hat, welche von der Überführungsfunktion in genau denselben Zustand und dieselbe Kopfposition überführt werden?

Danke, --Abdull 01:36, 3. Sep. 2010 (CEST)

Hallo Abdull,

• Das Eingabealphabet ist das Alphabet, aus dem die Symbole der Eingabe stammen können. Eine Turing-Maschine kann deshalb Wörter über einem Alphabet akzeptieren oder verwerfen. Auch, weil das Eingabealphabet eindeutig festlegt, welche Symbole als Eingabe zu verstehen sind, muss es eine Turing-Maschine charakterisieren.
• $\Gamma$ ist das endliche Bandalphabet, die Schreibweise ist leider etwas ungeschickt (wird geändert)
• F ist hier die Menge der Endzustände. Allerdings würde auch ein Endzustand reichen (siehe nächster Punkt). Jedenfalls sind Endzustände und akzeptierende Zustände hier das gleiche (siehe ebenfalls nächster Punkt).
• Für Turingmaschinen gibt es etliche richtige Definitionen. Ausgerechnet die Definition im Artikel ist unvollständig. Wenn eine Turingmaschine einen Endzustand erreicht, hält sie an und akzeptiert das Eingabewort. Deshalb ist Endzustand und akzeptierender Zustand meist das gleiche. Da die Maschine anhält, genügt ein akzeptierender Zustand. Die Frage ist, wann die Maschine ein Wort nicht akzeptiert. Entweder definiert man einen zweiten Endzustand, dessen Erreichen ein Verwefen des Eingabewortes bedeutet – womit Endzustand und akzeptierender Zustand nicht mehr gleichbedeutend wären. Oder man sagt, wie hier wohl beabsichtigt (aber nicht definiert), dass die Übergangsfunktion partiell ist und es Konfigurationen gibt, aus denen sie sich nicht mehr herausbewegen kann, weil kein Übergang definiert wurde. In diesem Fall bedeutet nicht akzeptieren, dass die Maschine auf diese Weise stecken bleibt.

--Zahnradzacken 20:24, 29. Okt. 2010 (CEST)

Grundsätzliche Überarbeitung

Hallo zusammen, ich bin gerade auf diesen Artikel gestoßen und finde ihn doch arg verbesserungswürdig. Einige Punkte:

• Die Einleitung ist nicht sehr erhellend. Der letzte Teil ist meiner Ansicht nach schlicht falsch, die Church-Turing-These sagt nichts über die Fähigkeiten des Menschen an sich aus
• Die Erklärung, wann die TM ein Wort ablehnt, ist ziemlich unverständlich
• In der Definition wird davon gesprochen, dass ein Wort akzeptiert wird, in den Beispielen wird eine Funktion berechnet. Entweder sollte man sich da zwei verschiedene Modelle von Turingmaschinen gönnen oder das Akzeptieren auf die Berechnung der charakteristischen Funktion zurückführen. Gibts da Präferenzen?
• Die Reihenfolge der Abschnitte ist ungünstig. Warum wird erst auf den Fleißigen Biber eingegangen, bevor ganz am Schluss geschrieben wird, dass durch TMs Sprachen entschieden werden?
• Sowohl sprachlich als auch typographisch muss der ganze Artikel überarbeitet werden

Bevor ich mich jetzt in meinem stillen Kämmerlein hinsetze und das umarbeite möchte ich mich gerne umhören, wer hier noch so mitliest. Dann könnte man vielleicht einige Grundsatzentscheidungen treffen und dann gemeinsam arbeiten. Würd mich freuen, was zu hören! -- NilsV 00:26, 28. Jan. 2011 (CET)

Deine Vorschläge klingen gut. Das mit der Church-Turing-These sollte in der Tat umformuliert werden. IIRC gibt es zwar in der Tat die starke Vermutung, dass auch Menschen nur church-/turing-berechenbare Probleme entscheiden können (und das sollte ruhig in den Artikel rein), allerdings wird diese Vermutung nicht von der Church-Turing-These selbst aufgestellt. Bezüglich der Modelle würde ich es der Einfachheit halber auf das Akzeptanzproblem reduzieren und in einem ausführlichen Abschnitt darlegen, wie man eine Berechnung auf ein Akzeptanzproblem zurückführen kann und somit beide "Arten" von Turingmaschinen eigentlich gleich mächtig sind. Allerdings bin ich kein theoretischer Informatiker und werde mich daher ziemlich zurückhalten, da ich Angst habe, am Ende etwas Falsches reinzuschreiben (...und zu faul bin, im Papadimitriou nachzuschlagen;-).--Wutzofant (grunz) 17:01, 28. Jan. 2011 (CET)

Ich lese auch mit und finde Wutzofants Vorschlag gut. Kenne TMs aber auch nicht zu gut, um die Präferenzen zu setzen.

Die Artikelstruktur ist natürlich mit der Zeit so gewachsen und vermutlich nicht oft hinterfragt worden. Eine sinnvolle Umstellung ist also sehr willkommen. Bzgl. Church-Turing-These: Orientiert sich der Begriff "intuitiv berechenbar" nicht gerade an dem Menschenmöglichen? So wie es der Wikipedia-Artikel darstellt, stellt die These keine Vermutung über den Menschen an, sondern nur über Maschinen anhand eines schwammig formulierten, menschlichen Vorbilds. Sollte das nicht zutreffen, wäre eine Korrektur des Artikel zur These dringlicher.

Die Erklärung, wann die TM ein Wort ablehnt, habe wohl ich geschrieben (zumindest, sofern du den Abschnitt 2.2 Berechnung meinst). Was ist daran unklarer als die vorangehende Definition? Ich sehe auch nichts von Funktionsberechnung in den Beispielen. Das Wort ([nicht-]akzeptierende) Berechnung ist der deutschen Ausgabe von Hopcroft/Motwani/Ullmann sowie dem Buch von Hromkovič entnommen. --Zahnradzacken 17:26, 28. Jan. 2011 (CET)

Schön, dass es noch andere Interessierte gibt ;) Zur Church-Turing-These: Die sagt aus, dass alle Funktionen, die von einer beliebigen Maschine berechnet werden können, auch von einer Turingmaschine berechnet werden können. Eine TM ist also ein formales Modell für den Begriff Algorithmus. Ich denke schon, dass der Mensch grundsätzlich das Halteproblem lösen kann, allerdings muss man jede Eingabe gesondert betrachten, da ist also nichts mehr mit automatisch entscheiden. Zu der Ablehnung von Wörtern: Mir fehlt im Moment nicht die Erklärung, wann die Berechnung endet, wenn man nicht in einen Endzustand gelangt. In dem Abschnitt Beispiel ist dann eine Turingmaschine angegeben, die eine Funktion berechnet, irgendwas mit Einsen verdoppeln.

Ich finde Wutzofants Idee auch gut, vielleicht kann man für TMs, die Funktionen berechnen, ja auch eine angepasste Definition angeben (mit der Anmerkung, dass die ineinander überführbar sind). Nur wie packt man das ganze an? Direkt im Artikel arbeiten oder im Benutzerraum eine Arbeitskopie erstellen? Wird ja schon ein paar Tage dauern, den Artikel umzuschreiben.. -- NilsV 18:15, 28. Jan. 2011 (CET)

Die Welt geht nicht zugrunde, wenn man die Veränderungen direkt am Artikel vornimmt. Wenn du aber schon eine Idee hast, die einen radikalen Umbau vorsieht, wäre der BNR vielleicht doch gut. Fehlt dir die Erklärung oder nicht? (Sie befindet sich im Abschnitt "Intuition", könnte aber etwas formaler auch nochmal im Abschnitt "Berechnung" stehen). Das Beispiel bezieht sich hauptsächlich auf die Aussage im Abschnitt Intuition, dass aus der Eingabe eine Ausgabe wird. Eine Ausgabe gäbe es auch, würde die TM das Wort irgendwann verwerfen. Im Beispiel sollte also auch auf den Aspekt des Akzeptierens eingegangen werden.

OT: Warum denkst du, dass der Mensch das Halteproblem lösen kann? --Zahnradzacken 18:53, 28. Jan. 2011 (CET)

Zum Halteproblem: Gegeben ein Programm (und evtl. eine Eingabe) investiere beliebig viel Geld in Menschen, die einen Beweis dafür suchen, dass das Programm hält oder nicht. Meine Behauptung: Nach beliebiger, aber endlicher Zeit hat irgend jemand die Lösung gefunden, auch wenn es mal ein paar hundert Jahre dauern kann. -- NilsV 21:00, 29. Jan. 2011 (CET)

Kleine Anmerkung zum 1.Abschnitt, 2.Absatz: "Die Church-Turing-These stellt die Behauptung auf, dass eine Turingmaschine alle Funktionen berechnen kann, die von heutigen Computern oder anderen theoretischen Maschinenmodellen (wie zum Beispiel dem Lambda-Kalkül) berechnet werden können." Hier könnte der Eindruck entstehen, dass die Äquivalenz von TM, Computern (Registermaschinen) und Lambda-Kalkül nicht bewiesen wäre. Auch besagt die These selbst ja nur, dass man mit der TM genau den (menschlich-intuitiven) Brechenbarkeitsbegriff gefasst hat. Genaugenommen folgt daraus dann erst (quasi als Korollar), dass andere (auch zukünftige) Modelle höchstens eine Teilmenge der Turing-berechenbaren Funktionen berechnen können. --89.247.88.51 18:16, 31. Jan. 2011 (CET)

Danke für die Anmerkung, das sollte natürlich nicht so klingen. Ich habe das mal geändert (ich hoffe verbessert). -- NilsV 00:39, 1. Feb. 2011 (CET)

Das Entscheidungsproblem

So konnte Turing zeigen, dass eine Turingmaschine das Entscheidungsproblem nicht lösen kann.

Welches denn? --Jobu0101 11:17, 19. Jul. 2011 (CEST)

Jenes, das im Absatz davor beschrieben wurde: en:Entscheidungsproblem, die Frage, ob eine prädikatenlogische Formel allgemeingültig ist (wobei die deutsche Beschreibung von der englischen etwas abweicht). --Zahnradzacken 18:50, 19. Jul. 2011 (CEST)

Abschnitt "Bedeutung in der Informatik"

Ich glaube, dass der Abschnitt "Bedeutung in der Informatik" irgendwie zu früh kommt, auch weil da die Aufmerksamkeit des Lesers auf Prädikatenlogik, Gültigkeit und Entscheidungsproblem gelenkt wird, was durchaus abschreckend wirken kann. Zudem ist all das gar nicht notwendig, um das Konzept der TM zu verstehen. Ich könnte mir deshalb vorstellen, den ganzen Abschnitt hinter das Beispiel zu verschieben. Was meint ihr? --89.247.126.23 14:56, 5. Nov. 2011 (CET)

Geändert. --Chricho ¹ 18:56, 10. Dez. 2011 (CET)

Erklärung für Nicht-Informatiker

Warum wurde das rausgeschmissen ? Ich finde es wichtig, das auch nicht-studierte wissen was für ein wichtiges Konzept das ist, desshalb hatte ich das vor Urzeiten mal reingenommen. Wie ich sehe wurde es dann von 62.134.230.134 total verwässert und später komplett rausgenommen. --matrixx 14.10.05

ALso ich habe zwar mit diesem Absatz nichts zu tun, aber ich finde das der ganze Artikel und vorallem die Einleitung auch für Nicht-Informatiker verständlich sein sollte - wie es eben in einer Enzyklopädie üblich ist. So ein Abschnitt sollte also unnötig sein, wenn der Artikel gut geschrieben ist. Inwieweit das der Fall ist wage ich mal nicht zu beurteilen, da ich wahrscheinlich zu "vorbelastet" bin. Ich verstehe ihn jedenfalls ganz gut. --87.123.34.199 18:53, 14. Okt 2005 (CEST)

Im Moment gibt es eine Einleitung, die ich unbefriedigend finde, die man aber nicht bearbeiten kann.

Also ich bin Nichtmathematiker und -informatiker und ich versteh ehrlich gesagt nur Bahnhof.

Das ist selbst für angehende Informatiker ziemlich unverständlich. Dieses ganze Formelgesülze gehört eigenlich nicht in ne Enzyklopädie, es fehlt einfach eine Definition, die selbst für absolute nicht-Informatiker ist. --Lennartb 21.11.07

Hallo Lennartb, du hast den Unverständlich-Baustein gesetzt. Ich habe den Abschnitt "Informelle Beschreibung" eben noch etwas überarbeitet/ausgebaut und halte die Einleitung und diesen Abschnitt auch für Nicht-Informatiker verständlich. Nenne bitte konkrete Stellen oder stell konkrete Fragen, ansonsten werde ich den Baustein demnächst wieder entfernen. -- Klara 15:47, 22. Nov. 2007 (CET)

Hallo Klara, die Einleitung halte ich jetzt ebenfalls für verständlich - danke dafür. Allerdings finde ich beispielsweise den Abschnitt "Formale Definition" bereits schon wieder verwirrend. Allein um die Einleitung zu verstehen, braucht man Mathematik-Kenntnisse die über das Klasse 13/Abitur-Mathe hinausgehen, bzw. muss sich erstmal die Definitionen von "deterministische" und "7-Tupel" zu Gemühte führen. Wenn ich mir für das Verständnis eines Enzyklopädie-Artikels, erst 5 andere Artikel durchlesen muss, finde ich das etwas...unglücklich.--Lennartb 20:40, 22. Nov. 2007 (CET)

Ich stimme dir zu, dass es schwierig ist, die formale Definition ohne Vorwissen/Übung zu verstehen. Es gibt nun aber Dinge, die können gar nicht ohne Vorwissen oder zumindest Vorarbeit (darunter fällt auch das Lesen von verlinkten Artikeln) verstanden werden. Denn man kann nicht in jedem Artikel bei Adam und Eva anfangen. Das wird besonders in abstrakten Bereichen (ganz extrem in der Mathematik) deutlich. Natürlich kann man damit auch nicht jede Kritik an der Verständlichkeit erschlagen, natürlich muss die Verständlichkeit erstmal das Ziel sein, darf aber auch nicht dazu führen, dass man ungenau wird (schon gar nicht im formalen Teil, dafür ist dann der informelle da). Bei komplizierteren Themen muss man aber vor allem darauf achten, dass es inhaltlich korrekt und verwendete Begriffe verlinkt sind. Wir haben in der Wikipedia die Möglichkeit, längere Artikel zu schreiben als in einer Enzyklopädie in Papierform, das muss ja nicht ungenutzt bleiben. Zu deiner konkreten Anmerkung: Die Funktionsweise, die hier beschrieben wird (im informellen sowie im formalen Teil) ist die der deterministischen Turingmaschine. Deterministisch heißt, dass es eine Funktion gibt, die für jeden Schritt eindeutig festlegt, was passiert. Das ist bei der nichtdeterministischen anders, es gibt verschiedene Möglichkeiten (daher ist es dort auch keine Funktion mehr, denn eine Funktion ordnet einem Element der Definitionsmenge immer eindeutig ein Element der Zielmenge zu). Das könnte man tatsächlich noch mehr ausformulieren und schon vorher sagen, dass es um hier um die deterministische Turingmaschine geht. Den Unverständlich-Baustein entferne ich dann jedenfalls mal. Viele Grüße -- Klara 23:45, 22. Nov. 2007 (CET)

Leute, ich finde das ärgerlich. Der Standard-Interessierte kommt hier doch her und denkt, eine Turingmaschine ist so eine Art ganz ganz alter Computer, älter als der 286er, vielleicht sogar älter als der Taschenrechner. Und er möchte es jetzt mal richtig erklärt bekommen. Zeige mir jemand 5 Menschen, die sich nach dem Abi nie mehr mit Informatik oder Mathematik befasst haben (und in Ihrer Freizeit auch nicht programmieren), die nach der Lektüre dieses Artikels auch nur den Hauch einer Vorstellung davon haben, was eine Turingmaschine ist. Wenn hier irgendjemand an mehr Verständlichkeit interessiert sein sollte, folgende Tipps, welche Fragen zu beantworten dieser Artikel meines Erachtens können müsste: Was ist eine Turingmaschine? Wie sieht die aus? Wie wird die bedient? Achso, es ist keine Maschine. Warum heißt sie dann so und was ist es sonst? Was kann man damit machen? Welche Berechnungen kann man damit durchführen? Was ist das besondere daran? Ist jeder Computer eine Turingmaschine? Ich fände auch ein Beispiel gut, in dem ganz genau und Schritt für Schritt gezeigt wird, wie eine Touringmaschine ein Problem löst. Soll sie doch zum Beispiel ausrechnen, vieviel 10% von 200 ist. Ist irgendeine der Fragen idiotisch? Nein- es gibt keine idiotischen Fragen, aber leider gibt es Wikipediartikel, die mich nicht schlauer machen als ich es zuvor schon war. Hier steh´ich nun usw. Goethe. Kennt hier eh keiner... ;-) Viele Grüße 84.61.110.87 03:04, 27. Feb. 2012 (CET)

Bitte, ihr klugen Menschen, macht diesen Artikel verständlicher!

Ich verstehe nur Bahnhof. Das geht schon ganz am Anfang los:

"Dieser Artikel beschreibt die Turingmaschine als Modell des mathematisch arbeitenden Menschen" Eine Turingmaschine ist ein Modell eines Menschen (der mathematisch arbeitet, also vermutlich rechnet)? Also z.B. eine Keramikskulptur einer nachdenklichen Person mit Zettel und Bleistift?

"Die Turingmaschine ist ein mathematisches Konstrukt zur formalen Beschreibung des Begriffes der Berechenbarkeit." Sie ist ein mathematisches Konstrukt? Ich dachte, ein wesentliches Element wäre dieses bewegliche Band? Wie kann ein mathematisches Konstrukt ein bewegliches Band haben?

"Man spricht von einer Turingmaschine als einem mathematischen Objekt" Ehrlich, ich habe keinen blassen Schimmer, was ein mathematischen Objekt ist.

"Die Turingmaschine gehört zu den grundlegenden Konzepten der theoretischen Informatik und wird heute zu einer allgemein anerkannten Definition der Berechenbarkeit verwendet: Eine Funktion wird berechenbar genannt, wenn eine Turingmaschine existiert, die diese berechnet." Prima. Was war nochmal eine Turingmaschine? 178.6.47.230 14:01, 12. Mai 2012 (CEST)

Zunächst zum "Anfang": Es handelte sich dabei um einen Hinweis, der nicht zum eigentlichen Artikel gehört, sondern normalerweise verwendet wird, um auf einen Artikel gleichen Namens mit anderem Inhalt zu verweisen. Da man namentlich und inhaltlich Turingmaschine mit Turing-Mechanismus nicht verwechseln kann, habe ich den Baustein entfernt. Die Formulierung "Modell des mathematisch arbeitenden Menschen" war einem späteren Satz in der Einleitung entnommen, ist aber weder zentral, noch halte ich sie für richtig. Deshalb habe ich auch den Satz entfernt.

Zum Verständnis: Das Band ist eine Verständnishilfe. Die "Turingmaschine" ist Theorie. Wenn man in der Theorie sagt "besteht aus X" und "X" ist etwas Materielles, dann heißt das eigentlich: "man stelle es sich als X vor". Dennoch gehört die mechanische Umschreibung natürlich zur Idee dazu.

Das "mathematische Objekt" ist verlinkt, verstehst du es mithilfe des Artikels? Allerdings ist der Satz ohne richtige Betonung nicht gleich verständlich: Es gibt die Turingmaschine als Konzept – und es gibt viele verschiedene Turingmaschinen als Objekte, die dem Konzept folgen.

--Zahnradzacken (Diskussion) 10:32, 13. Mai 2012 (CEST)

Ich denke der Einwand (die Unverständlichkeit für Leute, die das Konzept nicht eh schon verstanden haben) ist berechtigt. Seitdem ich hier mitlese (-schreibe) - seit ca. 2005 - taucht dieses Problem immer wieder auf und ich fürchte sogar, dass sich die Verständlichkeit durch die neueren Änderungen nicht wirklich verbessert hat. "Mathematische Konstrukte" und "Objekte" klingen zwar toll, tragen aber imo zur Unverständlichkeit bei. Ich denke es wäre für die Einleitung sinnvoll, sich noch einmal ins Gedächtnis zu rufen für wen der Text eigentlich geschrieben wird und gerade die mechanische Anschauung der Turingmaschine bietet doch Möglichkeiten dieses theoretische Konzept auch Laien zu vermitteln. Die starke Betonung des mathematisch-theoretischen Aspekts ist da wohl eher abschreckend (wenngleich sie grundsätzlich richtig ist). Ich finde, hier ist das durchaus besser gelöst. Dort wird erst im letzten Absatz der Einleitung darauf hingewiesen, dass diese Maschine ein rein mathematisches Konstrukt ist. --89.247.61.97 13:23, 13. Mai 2012 (CEST)

Abgesehen von dem Wörtchen "abstrakt" im ersten Satz. --YMS (Diskussion) 13:47, 13. Mai 2012 (CEST)

..was allemal besser ist als "mathematisches Konstrukt". --89.247.61.97 14:43, 13. Mai 2012 (CEST)

Ich hätte nichts gegen eine Verbesserung der Einleitung. Meine kleinen Änderungen fand ich nötig, waren aber keine Lösung für das Problem. Wenn ihr eine gute Übersetzung für "abstract computational device" wisst (ohne "device" als Gerät zu übersetzen), können wir darauf aufbauen. Der verlinkte Text ist angenehm zu lesen, aber erfüllt vielleicht nicht alle Bedingungen einer guten Einleitung. Man muss die Vorgeschichte lesen, bis man zu einem Satz gelangt, der den Kontext nennt und das Wort einordnet. Wenn man weiß, was ein Gedankenexperiment ist, weiß man beispielsweise bei Schrödingers Katze sofort, dass es in der Hauptsache nicht um ein Tier geht. Vielleicht gelingt das hier auch. --Zahnradzacken (Diskussion) 19:01, 13. Mai 2012 (CEST)

Huhu, das „mathematisches XY“ war ich. Und ich halte dies für absolut wesentlich. Der Verwirrung der IP nach zu urteilen („Ich dachte, ein wesentliches Element wäre dieses bewegliche Band? Wie kann ein mathematisches Konstrukt ein bewegliches Band haben?“) kann man dies wohl kaum zu deutlich hervorstreichen, wenn es trotz dieser aktuellen Betonung immer noch Zweifel daran seitens dieses „Test-Lesers“ gab. Es geht hier nicht um Bänder und nicht um Modellierung von irgendetwas sondern um ein rein formales, mathematisches Konzept (oder Konstrukt), bzw. im einzelnen um mathematische Objekte. Mir ist bewusst, dass der Artikel mathematisches Objekt eine Katastrophe ist und nicht zum Verständnis beiträgt, daraus einen ordentlichen Artikel mit ordentlichen Quellen zu machen, ist wohl hinreichend kompliziert. --Chricho ¹ ² 18:40, 13. Mai 2012 (CEST)

Deine Änderung von "Konstrukt" zu "Konzept" finde ich besser. Die Unterscheidung zwischen der TM und einer TM finde ich aber nicht gelungen. Nicht nur, weil mathematisches Objekt kein guter Artikel ist. Warum muss die Unterscheidung Konzept/Objekt gleich im zweiten Satz geschehen, wenn man noch gar nicht weiß, was die TM ist? Es ist nichts Bahnbrechendes, dass ein Konzept auch Ausprägungen hat. Jeder, der weiß, dass es nicht nur die Menge der natürlichen Zahlen, sondern auch einzelne Zahlen und spannende Teilmengen gibt, braucht keinen Hinweis auf mathematisches Objekt. Die anderen Leser holt man damit auch nicht hab. Bevor die Einleitung zwischen der und einer TM unterscheidet, würde ich dort gerne etwas über die Beschaffenheit der TM lesen. Nach deinem Revert werde ich das lieber erst diskutieren, bevor ich an den Artikel gehe. --Zahnradzacken (Diskussion) 15:17, 14. Mai 2012 (CEST)

Die Analogie zu den natürlichen Zahlen ist insofern falsch, als dass dort nicht von „der natürlichen Zahl“ gesprochen wird, sondern ausschließlich von natürlichen Zahlen und ihrer Menge. Ein gangbarer Weg wäre es in meinen Augen, in der Einleitung von „einer Turingmaschine“ bzw. „Turingmaschinen“ zu sprechen. Ein anschließendes „das Konzept wurde von Turing eingeführt“ o. ä. würde dann ohne weitere Erklärung verstanden, umgekehrt denke ich aber nicht. Deine Meinung? --Chricho ¹ ² 21:21, 14. Mai 2012 (CEST)

Die Analogie zu den Zahlen hat noch andere Mängel, aber der Punkt war, dass man von den Lesern erwarten kann, dass sie grundsätzlich zwischen Konzept und Instanz unterscheiden können. Man kann dann immer noch so ungeschickt formulieren, dass die grundsätzliche Fähigkeit untergraben wird.

Deshalb finde ich die Reihenfolge nicht wichtig, sondern dass mehr Worte als ein paar komprimierte Sätze erforderlich sind. Ich bin mit beiden Reihenfolgen einverstanden, aber wenn man mit "eine Turingmaschine/Turingmaschinen" beginnt, stellt sich wieder die Frage, womit man sie am besten umschreibt. Ein kurzer Versuch blieb bei mir ohne Erfolg (auch "abstract computational device" würde an der Stelle mehr verwirren als erklären). Letztlich wäre ich deshalb eher für den Ausbau des jetzigen Zustands. Hast du einen Vorschlag, zwischen den ersten und zweiten Satz noch etwas mehr zum Konzept zu schreiben? --Zahnradzacken (Diskussion) 23:24, 14. Mai 2012 (CEST)

„Turingmaschinen sind ein grundlegendes Konzept aus der theoretischen Informatik, die Begriffe wie die des Algorithmus und den der Berechenbarkeit mathematisch fassbar machen. Eine Turingmaschine ist ein mathematisches Objekt, das als Berechnungsvorschrift aufgefasst werden kann: Sie besteht aus Regeln, die angeben, wie mittels weniger, einfacher Operationen gegebene Zeichenketten (die zum Beispiel auch Zahlen darstellen können) schrittweise in andere überführt werden können. Die Regeln legen eindeutig fest, wie eine gegebene Zeichenkette umgeformt wird, sodass jede Turingmaschine eine Funktion von Zeichenketten nach Zeichenketten festlegt. Eine Funktion, für die eine Turingmaschine existiert, die eine Berechnung ihrer beschreibt, wird berechenbar genannt. Dieser Berechenbarkeitsbegriff hat dadurch besondere Bedeutung, dass die Operationen einer Turingmaschine auf intuitive Weise real durchführbaren Rechenoperationen entsprechen, und umgekehrt viele übliche intuitive Auffassungen von Berechenbarkeit von der Berechenbarkeit durch Turingmaschinen mit eingeschlossen werden. Das Konzept der Turingmaschine hat eine besonders einfache, minimalistische Struktur, welche eine gute mathematische Handhabbarkeit ermöglicht.“ Als Diskussionsgrundlage… Du kannst auch einfach nur den zweiten Satz als Vorschlag für deinen Zwischensatz nehmen. --Chricho ¹ ² 13:51, 15. Mai 2012 (CEST)

Gefällt mir als Grundlage. Den Nebensatz "sodass jede Turingmaschine eine Funktion von Zeichenketten nach Zeichenketten festlegt" würde ich gerne ungefähr so ergänzen: „Die Regeln legen eindeutig fest, wie eine gegebene Zeichenkette umgeformt wird. Anschaulich wird das Konzept als mathematische Analogie einer Maschine mit unendlichem Arbeitsband aufgefasst, auf dem die Maschine Zeichen lesen und schreiben kann und schrittweise ihre Position auf dem Band ändern kann. Damit beschreibt jede Turingmaschine eine Funktion von Zeichenketten nach Zeichenketten.“ --Zahnradzacken (Diskussion) 12:41, 19. Mai 2012 (CEST)

Der gesamte wiki-Artikel ist völlig daneben und unverständlich

Einige meiner Vorschreiber haben das ja auch schon angemerkt

Ergänzung:

die wikipedia sollte verständlich sein und kein Lehrbuch für eine Diplomarbeit (an ne, gibbet ja nich mehr...) Unglücklich und im deutschen Sprachraum unverständlich ist der Begriff Turing-MASCHINE.

Man stellt sich darunter irgendein Gerät vor, das vor sich hinrattert und keine "Rechen-Regel" (nicht signierter Beitrag von Frau.mahlzahn (Diskussion | Beiträge) 01:40, 30. Aug. 2012 (CEST))

Hallo! Ist es so besser (in der Einleitung)? Kannst du vllt. den ein oder anderen konkreten Punkt benennen, der unverständlich ist, bei dem man ansetzen kann? Zu dem „Maschine“: Daran, dass das Wort den Laien verwirren mag, kann man übrigens leider nichts ändern, das ist die übliche Bezeichnung, ist im Englischen auch nicht besser. Grüße --Chricho ¹ ² ³ 02:19, 30. Aug. 2012 (CEST)

Hallo! Wahrscheinlich ist das gesamte Feld für einen "einfach" gestrickten Menschen eh nicht verständlich. Man begreift das Problem (resp. die Fragestellung nicht) Frau.mahlzahn (Diskussion) 04:44, 30. Aug. 2012 (CEST)

Dass Problem ist, wie man den Begriff der Berechnung selbst mathematisch untersuchen kann. Weiß nicht, vllt. wird da eine gewisse Grundvorstellung von Mathematik, die viele nicht haben, vorausgesetzt? Ist das das Problem? --Chricho ¹ ² ³ 21:24, 30. Aug. 2012 (CEST)

Die Einleitung ist zu trocken, zu akademisch, vor allem: zu lang. Bevor der anschauliche Teil, die Erklärung, beginnt, ist der Laie schon abgehängt. Umstellen: Zwei, höchstens drei Sätze, etwa so: „Die Turingmaschine ist ein mathematisches Modell einer Rechenmaschine. Der Mathematiker Alan Turin entwarf es 1936, um zu untersuchen, was sich in der Mathematik berechnen lässt, und was nicht.“ Dann die Anschauung, der Abschnitt 1 mit dem Bild. Dann erst der übrige Sums aus der Einleitung, unter der Überschrift Mathematische Bedeutung. So ähnlich bekamen wir das auch im ersten Semester erklärt. Begriffe wie Algorithmus, und der langatmige Apparat mit der Zeichenumformung gehören nicht in eine Einleitung. Und schon gar nicht Hilberts Programm! Das gehört irgendwo ganz hinten hin – man kann die Turingmaschine erklären und verstehen, ohne von Hilbert ein Sterbenswörtchen gehört zu haben. – Die Einleitung bläst die Backen auf, versucht zu imponieren, statt zu erklären. --Mussklprozz (Diskussion) 22:05, 30. Aug. 2012 (CEST)

Dass das Konzept der Turingmaschine ein mathematisches Modell ist, ist aber schlicht und einfach sehr fragwürdig, sie dienen nicht dazu, bestimmte Beobachtungen best möglich mathematisch zu beschreiben. Und ja, Turingmaschinen sind akademisch. Und es wird damit geklärt, was überhaupt die Fragestellung ist, für die es das Konzept gibt. --Chricho ¹ ² ³ 23:00, 30. Aug. 2012 (CEST)

Da ich den Begriff "mathematisches Modell" kurz zuvor in den Artikel aufgenommen hatte, bin ich wohl in der Belegpflicht, der ich durch folgende Referenz gerne nachkommen möchte:

Eine Turing-Maschine ist ein „mathematisches Modell, um den Berechenbarkeitsbegriff formal zu erfassen.“ (Dirk W. Hoffmann: Theoretische Informatik, 2. aktualisierte Auflage, Carl Hanser Fachbuchverlag München 2011, ISBN 979-3-446-42639-9, S. 417). --Lex parsimoniae (Diskussion) 07:51, 31. Aug. 2012 (CEST)

Danke für den Beleg, Lex parsimoniae. Und Danke für Dein Argument, Chricho. Die Frage, was berechenbar ist und was nicht, ist auch für Laien hochinteressant. Laien sind unsere Zielgruppe. Fachmann und Fachfrau werden auf ihr Lehrbuch zur theoretischen Informatik zurückgreifen, und nicht auf die Wikipedia. Für Laien müssen wir bildhaft, vom Nutzen her, und pars pro toto beginnen. Meines Erachtens ist das ein Grundübel in vielen Wikipedia-Artikeln: bereits in der Einleitung 100% exakt sein wollen und möglichst viel hineinzupacken. „Das Geheimnis zu langweilen besteht darin, alles zu sagen.“ (Voltaire) Die wissenschaftlich exakte Definition erst dann folgen lassen, wenn der Leser eine bildhafte Vorstellung hat. Es geht nicht darum, sie wegzulassen, es geht um die Reihenfolge. – Gruß aus dem Neckarland, --Mussklprozz (Diskussion) 08:53, 31. Aug. 2012 (CEST)

Warum ich „mathematisches Modell“ für ungünstig halte (ja, man kann es so nennen, muss es aber nicht): Unter einem mathematischen Modell versteht man üblicherweise etwas, das der empirischen Beschreibung dient, der Simulation von Prozessen. Auf eine einschränkende Weise fasst man bestimmte abläufe mathematisch und versucht damit irgend etwas auszurechnen und vorherzusagen. Die Turingmaschine ist aber etwas völlig anderes als etwa ein Klimamodell. Was wird da modelliert? Das Denken? Rechenmaschinen? So recht passen will es nicht, jedenfalls dient die TM nicht der Simulation solcher. Systeme natürlichen Schließens etwa nennt man auch nicht Modelle des Denkens, ohne ins Philosophische abzugleiten. Der $\mathbb {R} ^{3}$ für sich ist auch nicht ein Modell des Universums, solang er nicht im Rahmen einer physikalischen Theorie einem solchen zugrundegelegt wird. Ich denke, dass man mit der Formulierung „mathematisches Modell“ mehr fehlerhafte Assoziationen weckt, als tatsächlich wichtige Information zum Ausdruck bringt. --Chricho ¹ ² ³ 12:32, 31. Aug. 2012 (CEST)

Modell des Denkens wäre größenwahnsinnig, aber Modell einer Rechenmaschine, in einem abstrakten Sinn, scheint mir nicht so abwegig. Ein Modell dient nicht notwendigerweise der Simulation, sondern kann auch der Veranschaulichen dienen, im rein statischen Sinne. Wir brauchen aber nicht an dem Wort zu kleben. Welchen besseren Begriff gibt es, um einem Laien klarzumachen, dass da keine Maschine vor sich hinklappert, sondert ein Gedankenkonstrukt untersucht wird? --Mussklprozz (Diskussion) 13:49, 31. Aug. 2012 (CEST)

Würde er nach dem Lesen der aktuell vorhandenen ersten zwei Sätze auf die Idee kommen, dass da etwas vor sich hinklappert? --Chricho ¹ ² ³ 14:05, 31. Aug. 2012 (CEST)

Er würde eher Zähigkeit als Klapprigkeit wahrnehmen, fürchte ich. ;-) Entschuldige bitte – konnte nicht widerstehen – ist nicht persönlich gemeint.Im ersten Satz der Stolperstein Algorithmus. Der zweite Satz nicht nur ein Stolperstein, sondern eine Mauer. Unter einem „mathematischen Objekt, das als Berechnungsvorschrift aufgefasst werden kann“, kann sich der Laie nichts vorstellen. Gruß, --Mussklprozz (Diskussion) 15:48, 31. Aug. 2012 (CEST)

Eine Sache zum „mathematischen Modell“ noch: Heute mag man das als Modell von Rechenmaschinen, um über „statische Eigenschaften“ zu sprechen, ansehen können. Damals ging das Konzept jedoch aus der Mathematik hervor, aus eher philosophischen Überlegungen zur Berechnung. Vielleicht kann man gut dafür argumentieren, dass der Modellbegriff einen wesentlichen Punkt des Konzeptes zum Ausdruck bringt, aber es erscheint mir unsicher und zudem eben falsche Assoziationen weckend. Weiter im Text: Die Frage, die ich mir jetzt stelle, ist: Was möchte man dem Leser in der Einleitung sagen? In der jetzigen Version sind es die folgenden Punkte:

1. Fachgebiet
2. Ziel: „mathematisch fassbar machen von …“
3. Eine Turingmaschine (war vorher nicht in der Einleitung zu finden)
4. Rein mathematisches Objekt (sie „macht“ eben nichts, sondern es werden einfach Begriffe darauf definiert, wie ein Lauf o. ä., deshalb „das als Berechnungsvorschrift aufgefasst werden kann“)
5. Allgemeine Beschreibung: Regeln zur Zeichenumformung
6. Informelle „Bandbeschreibung“
7. Berechnete Funktion
8. Rolle als Grundlage zentraler Begriffe (wie Punkt 2 dadurch erreicht wird)
9. Bezug zu Rechnern und Intuition
10. Mathematische Einfachheit (in Abgrenzung von typischen Programmiersprachen etc. (steht da im Moment nicht so explizit))
11. Erfindung
12. Hintergrund der Erfindung (Entscheidungsproblem, Hilbertprogramm)

Was erscheint euch dort besonders wichtig/entbehrlich? --Chricho ¹ ² ³ 16:24, 31. Aug. 2012 (CEST)

Hallo Chricho. Ich habe nicht geschrieben, dass die TM ein allgemeines mathematisches Modell ist. Ich habe geschrieben, dass sie ein mathematisches Modell zur formalen Erfassung des Begriffs der Berechenbarkeit ist, also ein spezielles für diesen Zweck, womit Deine Frage hierzu beantwortet wäre. Und dabei beziehe ich mich auf Dirk W. Hoffmann, der neben dem zitierten Buch auch noch eines über die Gödel'schen Unvollständigkeitssätze und die Grenzen der Mathematik geschrieben hat, der es also wie kaum ein anderer wissen muss.

Und genau darum geht es bei der TM. Sie wurde von Turing konzipiert, weil er die Berechenbarkeit formal (in einem mathematischen Modell) erfassen wollte. Daher sollte dies der erste Satz in der Einleitung sein.

Hallo Mussklprozz. Ich denke, wir sollten beides anstreben: Eine formal korrekte Definition UND die zugehörige allgemeinverständliche Erläuterung.

@beide: Viel mehr gehört meiner Ansicht nach nicht in die Einleitung. Ein Satz Definition und ein bis zwei Sätze über die Motivation und Entstehungsgeschichte. Alles andere sollten wir erst in den betreffenden Kapiteln behandeln, wobei wir in einem neuen ersten Kapitel zunächst die grundsätzliche Funktionsweise allgemeinverständlich beschreiben sollten.--Lex parsimoniae (Diskussion) 20:47, 31. Aug. 2012 (CEST)

Nur zum Punkt „mathematisches Modell“: Nur weil man einen Ausdruck verwenden kann und es gemacht wird, muss man es nicht tun. Ich habe oben Gründe dagegen aufgeführt, das Ziel kann man auch anders darstellen (was auch gerade im Moment der Fall ist). --Chricho ¹ ² ³ 20:53, 31. Aug. 2012 (CEST)

Unausgegorene Idee: Turingmaschinen spielen ja nicht nur in Sachen Berechenbarkeit eine Rolle, sondern auch in Richtung Komplexitätstheorie. "Anzahl der Schritte einer TM" ist ein direkt brauchbares Maß. Ähnliches kann man z.B. vom Lambdakalkül nicht ohne weiteres behaupten, da etwa ein Betareduktionsschritt superkompliziert sein kann.

Ich vermute mal, wenn man versucht, auch diesen Aspekt in der Einleitung anzuschneiden, und sich nicht auf Berechenbarkeit beschränkt, würde die Einleitung automatisch viel laientauglicher (und vielleicht auch kürzer) werden. --Daniel5Ko (Diskussion) 02:07, 1. Sep. 2012 (CEST)

Ja, das ist in der Tat auch ein Punkt bei der Turingmaschine (wobei man für alles, was unter Polynomialzeit etwas unterscheiden können soll, eher Registermaschinen benutzt). Wie durch zusätzliche Erwähnung einer weiteren Motivation und der Länge eines Laufes als Laufzeit die Verständlichkeit steigt, sehe ich aber nicht direkt. --Chricho ¹ ² ³ 02:37, 1. Sep. 2012 (CEST)

Es soll ja nicht einfach eine zusätzliche Motivation erwähnt werden, sondern diese Erwähnung selbst soll vollständig verständlich sein. Mit diesem konkreten Ziel vor Augen fällt es vermutlich leichter, zu entscheiden, was denn nun wichtig ist. --Daniel5Ko (Diskussion) 03:14, 1. Sep. 2012 (CEST)

Man beachte, dass dieses Komplexitätsmaß (Anzahl Übergänge) nur in sehr beschränktem Rahmen Anwendung findet, während der Berechenbarkeitsbegriff sehr allgemein ist. Man müsste dann schon etwas in der Richtung „in manchen Fällen dient sie auch der mathematischen Beschreibung von Laufzeiten“ schreiben. --Chricho ¹ ² ³ 12:47, 1. Sep. 2012 (CEST)

Hallo Chrichro, prima Vorschlag, die einzelnen Fakten aufzudröseln und zu entscheiden. Also:

1: ja

2: meinst Du „mathematisch fassbar machen von … Berechenbarkeit“? Dann ja.

3: ja

4: inhaltlich ja, aber nicht mit der Formulierung „mathematisches Objekt, das als Berechnungsvorschrift aufgefasst werden kann“

5-8: nein

9: Bezug zu Rechnern ja, Bezug zu Intuition nein

10: Eventuell, Tendenz zu nein.

11: Eventuell. Dann aber nur kurz die Namen Alan Turing und das Jahr erwähnen, keine weitschweifige Ausführung.

12: Keinesfalls.

--Mussklprozz (Diskussion) 05:17, 1. Sep. 2012 (CEST)

@Lex parsimoniae: Welche Form von formal exakter Definition stellst Du Dir vor? „Eine Turingmaschine ist ein Quintupel T = (Q; Σ; I; q; F= ..., wobei Q = ...“ – So etwas bitte auf keinen Fall in der Einleitung, die Leser rennen schreiend weg. ;-) Sondern in einem eigenen Abschnitt Mathematische Definition. Gruß, --Mussklprozz (Diskussion) 05:35, 1. Sep. 2012 (CEST)

So meinte ich das natürlich nicht, sondern so, wie ich es oben schon vorgeschlagen hatte:

„Eine Turing-Maschine ist ein mathematisches Modell, um den Berechenbarkeitsbegriff formal zu erfassen.“ Dach könnte folgen: „Sie wurde benannt nach ihrem Erfinder Alan Turing , der sie 1936 erstmals vorstellte. Das Prinzip der Turing-Maschine ist Grundlage unserer modernen Computer und spielt eine wichtige Rolle in der Theoretischen Informatik, Berechenbarkeitstheorie, ...“ (Ich hätte auch nichts dagegen, wenn zusätzlich die Komplexitätstheorie genannt werden würde.) --Lex parsimoniae (Diskussion) 12:34, 1. Sep. 2012 (CEST)

Grundlage moderner Computer? Inwiefern denn bitte das? Der erste Satz ist irreführend: Eine Turingmaschine sorgt nicht dafür, den Berechenbarkeitsbegriff formal zu fassen, eine Turingmaschine ist ein Algorithmus (in formaler Form), und das Gesamtkonzept erlaubt es, Berechenbarkeit formal zu fassen. Wenn man das nicht hervorhebt, versteht man nicht einmal die Sprechweise „eine Turingmaschine“ etc. --Chricho ¹ ² ³ 12:47, 1. Sep. 2012 (CEST)

... insofern als unsere modernen Computer dieselbe Berechnungsstärke haben wie Turingmaschinen. Computer sind Turingmaschinen. Man kann einen Computer durch eine Turingmaschine simulieren und umgekehrt. Die Grundlagenliteratur, in der all dies steht, hatte ich oben bereits erwähnt.

Der erste Satz ist nicht irreführend, sondern präzise. Er steht so in der oben angegebenen Fachliteratur. Selbst im Taschenbuch der Informatik, das sich an Quereinsteiger wendet, steht ebenfalls "mathematisches Modell".

Auf welche Quellen beziehst Du Dich bei Deinem Standpunkt?--Lex parsimoniae (Diskussion) 13:14, 1. Sep. 2012 (CEST)

Tut mir Leid, ich habe natürlich keine Literatur, in der steht „die Verwendung des Ausdrucks ‚mathematisches Modell‘ im ersten Satz eines Enzyklopädieartikels zu Turingmaschinen ist nicht zu empfehlen“, was soll also bitte die Frage? Und das mit der Berechnungsstärke ist a) nur eine informelle und idealisierte Vorstellung und b) nicht hinreichend, um von „Grundlage unserer modernen Computer“ sprechen zu können. Unsere Computer bauen auf Turingmaschinen genauso wenig auf wie auf μ-Rekursion. --Chricho ¹ ² ³ 13:53, 1. Sep. 2012 (CEST)

Hallo Chricho. Wenn Du Deine Aussagen nicht durch Literatur belegen kannst, dann nehmen wir gerne meine, denn die sind belegt.

Dein letzter Satz hat bei mir folgende Frage aufgeworfen: Wäre es denkbar, dass Du die Turingmaschine mit einer Turing-berechenbaren Funktion verwechselst, zu der die von Dir genannte μ-Rekursion gehört?--Lex parsimoniae (Diskussion) 14:17, 1. Sep. 2012 (CEST)

Nein, man muss nicht jeden Satz aufnehmen, der sich belegen lässt. Und nein, ich verwechsle da nichts, aber was das heißen soll, dass moderne Computer auf Turingmaschinen aufbauen sollen, hast du mir immer noch nicht erklärt. --Chricho ¹ ² ³ 14:49, 1. Sep. 2012 (CEST)

Ich habe es Dir bereits erklärt: Moderne Computer sind Turingmaschinen. Eine kurze Begründung habe ich oben bereits gegeben. Das lernt aber nun wirklich jeder Informatikstudent spätestens im zweiten Semester.

Ausführlichere Erläuterungen findest Du in o.g. Fachliteratur oder gerne in Kürze auch hier bei Wikipedia, vorausgesetzt, meine Arbeit hier wird nicht wieder von jemandem verändert, der nach diesen absoluten Grundlagen fragt und eine Turingmaschine mit einer Turing-berechenbaren Funktion verwechselt.--Lex parsimoniae (Diskussion) 15:28, 1. Sep. 2012 (CEST)

Das steht da mit Sicherheit so nirgends. Ich halte dagegen: Moderne Computer sind Polynome mit ganzzahligen Koeffizienten (wenn dir μ-Rekursion nicht gefällt, dann eben so; ich habe es übrigens nicht verwechselt, ich bezog mich auf die syntaktische Beschreibung einer μ-rekursiven Funktion, nicht auf die Funktion selbst). Solche Sätze sind einfach nur unsinnig. --Chricho ¹ ² ³ 17:04, 1. Sep. 2012 (CEST)

Männer, Ihr driftet ins Fachlich-Spezielle ab. Das Thema war Verständlichkeit. Können wir bitte die großen Züge der Einleitung klären, entlang Chrichros Auflistung oben?

@Chricho: Dann versuch doch mal, mit einem Polynom eine Turingmaschine zu simulieren.

@all: Wenn wir uns grundsätzlich darauf einigen können, uns inhaltlich an die einschlägige Fachliteratur zu halten, bin ich dabei. Dann können wir auch gerne anhand Chrichos Liste darüber diskutieren, welche Punkte in die Einleitung aufgenommen werden sollen. Wenn hier allerdings Theoriefindung betrieben werden soll, bin ich raus.--Lex parsimoniae (Diskussion) 11:57, 2. Sep. 2012 (CEST)

@Lex parsimoniae Das geht über den von mir oben verlinkten Satz von Matijassewitsch. Dennoch sind moderne Computer keine ℤ-Polynome und basieren auch nicht darauf. Und sich zu überlegen, dass eine Wortwahl vielleicht mehr Verwirrung stiftet als einzuordnen hilft, ist keine TF, sondern notwendig zur Gestaltung eines enzyklopädischen Textes.

Wenn man in der Einleitung die Details zu Ausführung, berechneter Funktion und Geschichte weglässt, wäre ich dafür, die Abschnitte mit der informellen Beschreibung und der Bedeutung etwas umzustrukturieren: In der informellen Beschreibung schon die Formulierungen dermaßen abändern, dass klar wird, dass man mit einer Turingmaschine die Berechnungsvorschrift meint. Und dort das mit der berechneten Funktion besser erklären. Bei der Bedeutung sollte man das Entscheidungsproblem ausklammern und in einen eigenen Geschichtsabschnitt packen (das ist natürlich nach wie vor relevant, aber wichtiger ist, dass dadurch allgemeine Begriffe festgelegt werden, und sollte erst dahinter komen). Zu Punkt 2: Ich meinte auch mathematisch fassbar machen von Algorithmus, man könnte es ja Berechnungsvorschrift nennen, wenn Algorithmus zu böse klingt. --Chricho ¹ ² ³ 12:39, 2. Sep. 2012 (CEST)

Zitat:

@all: Wenn wir uns grundsätzlich darauf einigen können, uns inhaltlich an die einschlägige Fachliteratur zu halten, bin ich dabei.

Zitat Ende.

WIKIPEDIA ist eben KEINE Fachliteratur. Ich glaube, einige verstehen das nicht. (nicht signierter --Frau.mahlzahn (Diskussion) 01:34, 5. Sep. 2012 (CEST)--Frau.mahlzahn (Diskussion) 01:35, 5. Sep. 2012 (CEST)

Entschuldige bitte, dass ich helfen wollte, eine leicht verständliche Formulierung zu finden, die inhaltlich trotzdem dem Stand der Fachliteratur entspricht.

Wenn Du eine leicht verständliche Formulierung suchst, die garantiert in keinem Fachbuch vorkommt, könntest Du sagen: „Eine Turingmaschine ist reisetaugliches Motorrad, korrekte Schreibweise: Touring-Maschine.“ Aber in den Artikel können wir das so nicht aufnehmen, denn hier sollte grundsätzlich alles quellenbasiert und auf Basis zuverlässiger Literatur belegt sein, siehe Wikipedia:Belege und Wikipedia:Keine_Theoriefindung.--Lex parsimoniae (Diskussion) 15:56, 5. Sep. 2012 (CEST)

Neugestaltung der Einleitung

Wie bereits in anderen Abschnitten diskutiert, ist die Einleitung in ihrem jetzigen Zustand keine Einleitung, sondern ein (nicht geglückter) Versuch einer umfassenden Abhandlung des gesamten Themas. Ich schlage also vor, dass diejenigen, die sehr an der einen oder anderen Formulierung der jetzigen Einleitung hängen, diese bitte in die entsprechenden Detail-Abschnitte einpflegen, damit sie bei einer grundlegenden Neugestaltung der Einleitung nicht verlorengehen. Folgendes wäre mein Vorschlag für eine neue, leicht verständliche und kurze Einleitung, die dem Stand der Fachliteratur entspricht:

Eine Turingmaschine ist ein einfaches mathematisches Modell für Computer. Es beschränkt sich auf wenige elementare Operationen und ist dennoch stark genug, um damit alle Berechnungen durchführen zu können, die auf allen heute existierenden Computern möglich sind. Die Turingmaschine wurde benannt nach ihrem Erfinder Alan Turing, der sie 1936 erstmals vorstellte und spielt eine wichtige Rolle in der Theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie.

--Lex parsimoniae (Diskussion) 12:50, 20. Sep. 2012 (CEST)

Siehe bitte hier, die Einleitung soll durchaus eine Zusammenfassung der wichtigsten Aspekte des Artikels liefern. Sie darf durchaus länger als das sein. Die jetzt vorgeschlagene Einleitung ist nicht gerade zufriedenstellend in Anbetracht der Punkte, die vorher diskutiert wurden:

• Zu starker Bezug zu Computern.
• Fehlende Klarstellung, was eine Turingmaschine ist.
• Der Ausdruck mathematisches Modell verwirrt (s. o.). Und welcher Aspekt wird modelliert?
• Motivation wird nicht dargestellt.
• Verwirrende Formulierung, eine Turingmaschine führt keine Berechnungen durch. --Chricho ¹ ² ³ 15:46, 22. Sep. 2012 (CEST)

Mir ist schon klar, worauf Du hinaus willst. Aber wenn wir damit fertig sind, sieht die Einleitung wieder genauso aus wie jetzt, wofür sie aber zurecht kritisiert wurde.

• Als zu stark würde ich den Bezug zu Computern nicht bezeichnen, sondern angesichts der grundlegenden Thematik als angemessen.
• Was eine TM ist, steht drin. Weitere Details gehören nicht in eine Einleitung, sondern ins jeweilige Kapitel.
• Mathematisches Modell wird sowohl in der speziellen Fachliteratur gebraucht als auch in einem einfachen Taschenbuch der Informatik, das sich an Einsteiger richtet. Noch besser kann man dem Anspruch auf Korrektheit und leichte Verständlichkeit wohl kaum gerecht werden.
• Motivation wird durch ihre Fähigkeiten und Anwendungsbereiche sehr deutlich dargestellt. Wenn das nicht reicht, bitte Vorschlag.
• Verwirrende Formulierung könnte zutreffen. Ich bitte um einen Vorschlag.

--Lex parsimoniae (Diskussion) 12:45, 24. Sep. 2012 (CEST)

Nein, was eine Turingmaschine ist, steht nicht drin, das ist nämlich nicht ein Modell, sondern – mathematisch formalisiert – eine Berechnungsvorschrift. Und deshalb führt sie auch keine Berechnungen aus. Bevor ich mir überlege, was in die Einleitung soll, würde ich mir eine Stellungnahme zu dieser Frage des Aufbaus des darauf folgenden wünschen. --Chricho ¹ ² ³ 14:23, 24. Sep. 2012 (CEST)

Was meinst Du mit eine? Kann es sein, dass Du die TM primär aus dem Blickwinkel der Mathematik betrachtest? Wenn ja, dann fasse doch bitte Deine wichtigsten Aspekte mal leicht verständlich in einen Satz zusammen, so wie auch ich es tat. Wieso sollen Details wie der Satz von Matijassewitsch schon in der Einleitung erwähnt werden, wenn sie weder in den Definitionen der Fachliteratur noch in den Definitionen einfacher Informatikhandbücher stehen?--Lex parsimoniae (Diskussion) 21:39, 24. Sep. 2012 (CEST)

Der Satz von Matijassewitsch hat in der Einleitung natürlich nichts verloren, der gehört in den Artikel Rekursiv aufzählbare Menge oder Berechenbarkeit, ich wollte damit nur demonstrieren, wie absurd Aussagen wie „Turingmaschinen sind Computer“ sind, denn da könnte man genauso gut sagen „ℤ-Polynome sind Computer“, da die Konzepte eben äquivalent sind. Die wesentlichen Aspekte, die ich mir in der Einleitung wünsche, finden sich bereits in der aktuellen Einleitung (was nicht heißt, dass man die nicht kürzen sollte, Sachen auslagern…). Zum eine: Eine Turingmaschine ist nichts anderes als ein mathematisches Objekt, nämlich die Übergangsfunktion, welche man sich als Berechnungsvorschrift vorstellt, siehe momentane Fassung der Einleitung. --Chricho ¹ ² ³ 22:07, 24. Sep. 2012 (CEST)

„Turingmaschinen sind Computer“ hat niemand behauptet, ich sagte: „Computer sind Turingmaschinen“, umgekehrt gilt das natürlich nicht. Wenn Du das klären willst, mach bitte einen neuen Abschnitt auf.

Zurück zur Einleitung: Die bestehende Einleitung wurde aus meiner Sicht zurecht kritisiert. Ich habe einen Verbesserungsvorschlag gemacht. Willst Du jetzt mitwirken oder auf der alten bestehen? Wenn Du mitwirken willst, dann schreibe bitte etwas konstruktives in meinen Entwurf.--Lex parsimoniae (Diskussion) 22:41, 24. Sep. 2012 (CEST)

Zweite Grafik korrekt?

In der Grafik TuringBeispielAnimatedGIF.gif ist von Adressen die Rede. Ist das denn korrekt? Eigentlich müsste es doch an dieser Stelle 'Zustand' heissen; hätte auch den Vorteil, dass die Grafik dann zum Text passt. --FJannidis (Diskussion) 12:37, 28. Okt. 2012 (CET)

Ja, müsste es, die Bezeichnung Adresse ist unsinnig. --Chricho ¹ ² ³ 12:44, 28. Okt. 2012 (CET)

Tote Weblinks ?

Für mich ist heute (2013-06-13) dieser Weblink durchaus erreichbar: http://www.cs.princeton.edu/theory/complexity Die Inhalte sind dann unter "Draft of the book" erreichbar. Das "oblivious" in Kapitel 2.3.4 habe ich z.B. gefunden. Ich kann jedenfalls nicht sehen, wozu wir die Wayback-Maschine brauchen sollten.
--H.Marxen (Diskussion) 17:35, 13. Jun. 2013 (CEST)

Das ist komisch… Jetzt geht es bei mir auch, vorhin bekam ich nur eine 404-Seite… Magst Du aber vielleicht die Links korrigieren und dabei bitte auch gleich benennen? Beim zweiten habe ich Schwierigkeiten, wo ist der Remark 1.10? Wir sollten doch besser direkt auf die Seite(n) verlinken und nicht auf eine Übersichtsseite, wenn es möglich ist. Gruß und auch danke für die Benachrichtigung— Spuki ^Séance 17:48, 13. Jun. 2013 (CEST)

Habe die Links benannt und den Ort genauer bezeichnet. --H.Marxen (Diskussion) 18:54, 13. Jun. 2013 (CEST)

(BK) Ich musste echt ein Brett vor dem Kopf haben. Habe nun alles gefunden und korrigiert. Schau noch mal hin, ist so vielleicht noch besser? Gruß— Spuki ^Séance 18:56, 13. Jun. 2013 (CEST)

Gefällt mir. Kann so bleiben. --H.Marxen (Diskussion) 19:38, 13. Jun. 2013 (CEST)

(2014) Konfusionen und lange Reden, gar kein Sinn?

So ist der Artikel ist eine Katastrophe:

1 "Eine Turingmaschine modelliert die Arbeitsweise eines Computers." Duden: modellieren = bauen, bearbeiten, ein Modell herstellen. Wer Konfusion säht sollte keine Präzisionsartikel schreiben.

2."auf besonders einfache und mathematisch gut zu analysierende Weise" Das ist Phrasendrescherei der Extra-Klasse, willste dafür ein Setzen-6 oder Applaus für den ausgefeilten Nonsens?--91.34.201.122 20:18, 3. Jun. 2014 (CEST)

Weblink zu mangelhafter Javascript-Anwendung

Diese Anwendung funktioniert, kommt aber ohne einen Fetzen Bedienungsanleitung des Weges und ist in dieser Form eine Zumutung. --Mussklprozz (Diskussion) 23:28, 26. Jan. 2014 (CET)

---

Kopiert von BD:Zicane

Bitte lies Dir die Vorgaben für geeignete Weblinks auf den Seiten WP:Weblinks durch. Der von Dir eingestellte Link entspricht meines Erachtens nicht diesen Regeln. Allein die Tatsache, dass er Javascript erfordert, ist im Gegensatz zum Grundsatz keine Links, die Sondersoftware erfordern.
Ich werde nicht erneut eingreifen in den Artikel, aber vielleicht leuchtet Dir ja das System ein -:) (Editwars sind tunlichst zu vermeiden). Beste Grüsse --Fettbemme (Diskussion) 08:54, 24. Jan. 2014 (CET)

Der von mir gepostete Link führt zu einer sehr Leistungsfähigen Software um Turing Maschinen zu konstruieren und auszuführen. Für viele die sich mit dem Thema befassen könnte die Software von großem Nutzen sein. JavaScript ist neben HTML und CSS mittlerweile eine fundamentale Technologie des Internets und das sollte auch bei Wikipedia akzeptiert werden. Es ist verwerflich wenn Ajax Anwendungen nicht in Wikipedia Artikeln verlinkt sein dürfen.

WP ist immer noch keine Linksammlung. Und als ich diese Software ausprobiert habe, hat sie schlicht gar nichts getan: kein Button hat irgendwas bewirkt (außer dem "about"). --H.Marxen (Diskussion) 17:06, 24. Jan. 2014 (CET)

Das WP eine Linksammlung ist habe ich auch nicht behauptet. Zur Benutzung ist ein moderner Browser notwendig.

Ich verwende die aktuelle Version von Firefox, und auch damit ist die Anwendung nicht zu gebrauchen. Auch bei mir kommt statt Hilfe nur about, bei Set Tape kommt initial state not existing, die Überschrift lautet untitled, und keiner der übrigen Knöpfe bewirkt irgendetwas. Wikipedia ist keine Plattform für Bastelarbeiten von Anfängern. --Mussklprozz (Diskussion) 16:51, 25. Jan. 2014 (CET)

Kennst du dich denn mit Turing Maschinen aus? Bevor das Band gesetzt werden kann muss eine Maschine vorhanden sein. Dafür muss in der Zeichenfläche ein Graph erstellt werden.

Nein, hast Du nicht behauptet. Dein Verhalten, auf einem solchen Link zu bestehen, zu insistieren, läßt halt vermuten, daß Du diese Funktion "Linksammlung" hier für sehr wichtig hältst. In meinen Augen ist das bereits ein WP:Editwar, was mir sehr unangenehm ist. Aber ich finde nicht, daß Du dich einfach gegen alle Sichter (und ihr Verständnis der Regeln) durchsetzen darfst. Wenn Du die Regeln nicht magst, sie gar „verwerflich“ findest, solltest vielleicht an geeigneter Stelle anregen, daß sie geändert werden. Dann würde sich mein Verhalten ebenfalls ändern: ich versuche mich an die Regeln zu halten. Vielleicht findest Du ja genügend Gleichgesinnte, daß die Regeln in deinem Sinne geändert werden.

Mein Browser ist vielleicht nicht der neueste, aber Javascript kann er schon, und er genügt völlig, um in WP zu lesen, zu schreiben, und zu sichten. Daß er dennoch mit jener Web-Seite nicht klar kommt, ist meiner Meinung nach ein Qualitätsmangel (der Webseite).
--H.Marxen (Diskussion) 17:00, 25. Jan. 2014 (CET)

Ich traue dir zu, bestehende Regeln in Frage zu stellen. Und das muss man auch manchmal tun. Ajax Anwendungen setzen nun mal Technologien (HTML5) voraus, die nicht in ältern Browsern enthalten sind. Browser sollten aber schon aus Sicherheitsgründen aktuell sein.

Es wäre nett, wenn Du Deine Beiträge auch hier signierst (mit zwei Minus und 4 Tilden). Ist für die anderen dann besser lesbar. Danke.

Es geht nicht darum wer sich was traut. Ich habe auch nichts dagegen, wenn Du Regeln in Frage stellst. Nur zu. Aber Du machst ja was anderes: Du trittst nicht etwa eine Diskussion darüber an geeigneter Stelle los (was ich durchaus gut fände), sondern Du verstößt gegen die Regel, und insistiert, daß Du das darfst, indem Du Korrekturen rückgängig machst. Aber so geht das nun mal nicht: WP beinhaltet auch einen sozialen Prozeß um Konsens zu erzielen. Ohne Konsens gibt es lauter Editwars. Also erstellt man Regeln per Diskussion und Abstimmung. Das ist doch nicht schwer zu verstehen, oder?

Zur Web-Seite... „in der Zeichenfläche ein Graph erstellt“ ... also das ist keineswegs offensichtlich. Eine minimale Anleitung zur Benutzung wäre wirklich hilfreich. Ich konnte nicht mal was mit den meisten Piktogrammen anfangen. Was hälst Du von diesen niedlichen kleinen Blasen mit kurzen Texten, die solche Knöpfe „benennen“? Mein Browser macht das mit seinen Knöpfen, Deiner wahrscheinlich auch.
--H.Marxen (Diskussion) 22:43, 25. Jan. 2014 (CET)

Was ist das größere Übel: Gegen unsinnige Regeln zu verstoßen oder diese einzuhalten? Die Sichter, die meine Änderung rückgängig gemacht haben, hätten genauso gut überlegen können ob die Regel sinnvoll ist. Sie sind aber den bequemeren Weg gegangen. Aber in wessen Sinne soll das bitte sein?

Wie kann ich denn eine Änderung der Regeln in Gang setzen?
--Zicane 21:53, 26. Jan. 2014 (CET)

Na ja, den für Dich bequemeren Weg hast Du doch wohl auch gewählt. Das kannst Du schlecht anderen vorwerfen. Offenbar haben die anderen Beteiligten (inklusive meine Person) kein solches Bedürfnis danach, diese Regel zu ändern. Ich kann selber gut damit leben, kann aber verstehen, warum jemand andere Zielvorstellungen entwickeln mag. Aber ich werde mich nicht auf den Weg machen, Deine Wünsche zu vertreten, wo sie sich mit meinen nicht decken.

„eine Änderung der Regeln in Gang setzen“... habe ich selber noch nicht versucht, bin also nicht sicher. Ich würde wohl bei der Regel selber anfangen, also WP:Weblinks, und dort in die Diskussions-Seite sehen. Mag sein, Dein Thema wird da schon diskutiert, oder wurde schon mal diskutiert, dann ist sowas vielleicht ja schon im Gange. Ansonsten kann man auf solchen Diskussions-Seiten eben auch ein neues Kapitel anhängen, für ein neues Thema.
--H.Marxen (Diskussion) 23:04, 26. Jan. 2014 (CET)

Doch, ich verstehe etwas von Turingmaschinen. Mit etlichem Herumprobieren habe ich auch verstanden, dass und wie Deine Anwendung funktioniert. Glückwunsch in dieser Hinsicht. – Du, Zicane, hingegen scheinst nichts von den elementaren Regeln der Softwareergonomie zu verstehen oder zu halten. Eine Anwendung ohne einen Fetzen Anleitung, eine Anwendung, bei der der Nutzer raten und probieren muss, ist mangelhaft – auch wenn sie in logischer Hinsicht korrekt arbeitet. --Mussklprozz (Diskussion) 23:23, 26. Jan. 2014 (CET)

Ende Kopie

---

Ich kann (und darf) hier keine inhaltliche Entscheidung treffen. Wenn sich die Beteiligten darauf einigen, keinen weiteren Edit-War um diesen Link zu liefern, werde ich entsperren. --PaterMcFly Diskussion ^Beiträge 11:33, 27. Jan. 2014 (CET)

Wenn es nützt, kann ich mich von weiteren Sichter-Aktivitäten zu diesem Weblink fernhalten. Bin aber weiter bereit inhaltlich zu diskutieren. --H.Marxen (Diskussion) 14:40, 27. Jan. 2014 (CET)

Also zurück zum Inhaltlichen: Ich halte das von Zicane verlinkte Tool für schöner und vollständiger als die bereits unter den Weblinks verlinkten Javascripts, und allemal wesentlich barrierefreier als das ebenfalls dort bereits befindliche Java-Applet (anders als JavaScript erfordert das tatsächlich ggf. Zusatzsoftware). Die Dokumentation fehlt tatsächlich, was die Bedienung etwas unintuitiv macht, aber wie eine Turingmaschine grundsätzlich funktioniert, erklärt ja unser Artikel, und die Transferleistung, das dann bei einer ja nicht soo wahnsinnig komplexen GUI anzuwenden, halte ich für überschaubar. Fazit: Da ist noch Potential nach oben, und wir brauchen natürlich auch keine zehn verschiedenen Turingmaschinensimulationslinks, aber nach einer kurzen Analyse denke ich, dass - so kein grundsätzlich besserer, ganz neuer Weblink gefunden wird - Zicanes Link besser ist als das was wir bereits haben, und daher eher die Altlinks ausgedünnt werden sollten anstatt den neuen zu blockieren. --YMS (Diskussion) 14:56, 27. Jan. 2014 (CET)

So, wie die Seite derzeit daherkommt - ohne ein Stück Anleitung oder Dokumentation, und das bisschen, was auf der Seite lesbar ist, zudem noch auf Englisch (von der Überschrift "untitled" will ich jetzt gar nicht anfangen) - erfüllt sie in keiner Weise die Anforderungen an einen Weblink und "vom Feinsten" ist sie schon gar nicht. Was die JavaScript-Problematik angeht: Ich für mein Teil würde das in so einem Fall nicht als Ausschlussgrund ansehen. --Reinhard Kraasch (Diskussion) 15:51, 27. Jan. 2014 (CET)

Vielleicht rafft sich Zicane ja dazu auf, seinem Programm eine vernünftige Anleitung einzubauen, statt seine Zeit in eine Grundsatzdiskussion über WP:Web zu investieren. Dann ist der Fall nämlich zur allgemeinen Zufriedenheit erledigt. – Gruß aus Freiberg am Neckar, --Mussklprozz (Diskussion) 16:34, 27. Jan. 2014 (CET)

Die Beanstandungen der Sichter wurden behoben. --Zicane 17:09, 06. Feb. 2014 (CET)

Es ist besser, aber immer noch nicht gut. Ich bin ein Freund knapper Bedienungsanleitungen, aber diese ist zu lakonisch abgefasst. Es ist immer noch nicht ersichtlich, dass es eine Konstruktionsfläche gibt. Was hältst Du davon, diesem Bereich eine Überschrift zu verfassen – z. B. Construction Area? Der Text beim Create-Button sollte etwa so lauten: Click onto this symbol and then into the construction area to create a state. Bei Transition Mode entsprechend: Click onto this symbol, then connect two states by dragging the mouse, to create a transition between those two states. Und bitte, bitte, ersetze die hässliche Überschrift Untitled durch einen aussagekräftigen Titel. Dann sichte ich Deine Änderung mit dem größten Vergnügen. Gruß aus Freiberg am Neckar. --Mussklprozz (Diskussion) 21:38, 6. Feb. 2014 (CET)

Noch schicker wäre es, wenn die Hilfetexte beim Überfahren mit der Maus erscheinen würden. Das wäre dann die Kür. Mit Ajax ist auch das kein Hexenwerk. --Mussklprozz (Diskussion) 21:39, 6. Feb. 2014 (CET)

Die Frage lautet ja nicht: Ist die Anwendung frei von Mängeln oder nicht? Sie lautet: Bietet die Anwendung dem Leser des Artikels einen Mehrwert? Und diese Frage kann eindeutig mit ja beantwortet werden. Und daher bestehe ich auf die Beibehaltung des Links in dem Artikel. --Zicane 3:51, 07. Feb. 2014 (CET)

Du irrst. Lies WP:Web. Dort steht, dass es „vom Feinsten“ sein muss. Und das ist es im jetzigen Zustand noch nicht. Investiere lieber noch etwas Zeit in die Verbesserung, statt hier zu streiten. --Mussklprozz (Diskussion) 20:12, 7. Feb. 2014 (CET)

Das Problem ist nicht die Qualität der Software sondern deine Einstellung. Es gibt immer Gründe etwas nicht zu machen. Wenn du aber mal anfängst über Argumente für die Abbildung des Links zu nachzudenken und das Für und Wider abwägst, wirst du zu einer anderen Entscheidung gelangen. Und dann können wir die Diskussion auch beenden. --Zicane 0:24, 10. Feb. 2014 (CET)

Wenn Du dieser Meinung bist, dann ist die Dritte Meinung der geeignete Weg. Du versuchst es leider weiterhin per Editwar. Wenn Du so weiter machst, fängst Du Dir eine Vandalismusmeldung ein. Ich stelle den Fall jetzt bei der Dritten Meinung vor. --Mussklprozz (Diskussion) 18:51, 15. Feb. 2014 (CET)

Dritte Meinung

WP:Dritte Meinung: Die Anwendung ist nicht schlecht, aber im derzeitigen Zustand nicht verlinkbar. Wenn man sie ausfruft kommt man erstmal nicht weiter und muss mühsam stochern, bis etwas läuft. Sie wäre ok, wenn bereits eine Beispielturingmaschine vorgeladen wäre, so dass man nach dem Aufruf direkt auf run klicken könnte. Außerdem könnte man noch weitere Beispielanwendungen zur Auswahl stellen. Wenn man dann ein bisschen m it der Maschine gespielt hat, kann man daran rumeditieren und lernt dann, wie sie funktioniert. --Siehe-auch-Löscher (Diskussion) 09:20, 16. Feb. 2014 (CET)

Ich weiß nicht, ob diese Diskussion noch läuft, aber derzeit erscheint mir die Anwendung ziemlich gut bedienbar und intuitiv (wenn man weiß, was eine Turingmaschine ist und wie man sie darstellen kann). Eine Beispielanwendung wäre in der Tat gut, aber durch Rumprobieren kommt man auch so voran. --217.50.139.59 11:36, 16. Mai 2015 (CEST)

Akzeptierende(r) Zustand/Zustände - Widerspruch?

Oben im Artikel, im Abschnitt "informelle Beschreibung" steht:

"Bestimmte Zustände werden als „akzeptierend“, andere als „nicht akzeptierend“ definiert. Die Eingabe wird genau dann akzeptiert, wenn die Turingmaschine in einem akzeptierenden Endzustand endet."

Während weiter unten im Abschnitt "Formale Definition" im 7-Tupel die siebte Stelle nur $q_{f}$, ein einzelner Zustand ist. Wenn aber mehrere Zustände als akzeptierende Endzustände definiert werden können, müsste hier nicht eine Menge (z.B. $F$) stehen und beschrieben sein als

$F\subseteq Q$ sind die akzeptierenden Zustände

?

--217.50.139.59 11:25, 16. Mai 2015 (CEST)

Ja, etwas verwirrend ist das schon. Die informelle Beschreibung ist weiter zutreffend, und beschreibt das Prinzip, wie es ähnlich bei endlichen Automaten zu finden ist. Konkret modelliert man die Berechnungen bei Turingmaschinen dann aber doch so, daß ein einziger Halte-Zustand ausreichend ist. Der Unterschied liegt in der Modellierung der Termination: von der TM wird verlangt, daß sie aus eigenem Antrieb, bzw. auf Grundlage der Eingabe, beschließt, wann die Berechnung beendet ist, und sie hat das anzuzeigen, indem sie in den Haltezustand geht.

Bei endlichen Automaten modelliert man das Ende der Eingabe nicht mit, und die Berechnung ist stets fertig... für den Teil der Eingabe, der verarbeitet wurde. Würde man endliche Automaten ein explizites EOF-Symbol verarbeiten lassen, bräuchten sie auch nur noch einen akzeptierenden Zustand.

--H.Marxen (Diskussion) 19:33, 18. Mai 2015 (CEST)

Habt Ihr jetzt aneinander vorbei geschrieben oder bin nur ich etwas neben der Spur? ;-) Die IP spricht oben von dem letzten Satz des betreffenden Absatzes im Artikel; der Satz mit dem „akzeptierend“ und „nicht akzeptierend“. Du, @H.Marxen, beziehst Dich in Deiner Antwort auf den Absatz davor, nämlich der Möglichkeit, mehrere Endzustände zu haben. So wie ich das derzeit verstehe, sind „akzeptierend“ oder „nicht akzeptierend“ zusätzliche Attribute für einen Zustand und unabhängig davon, ob ein Zustand ein Endezustand ist oder nicht. Das wiederum würde bedeuten, dass man einem Endzustand die Information (das Attribut) mitgeben kann, ob der Output (also die Daten auf dem Speicherband nach dem Anhalten) gültig ist oder nicht.
Würde ja Sinn machen, doch in Stephen Cole Kleene's Introduction to Meta-Mathematics habe ich das so allerdings nicht gefunden – und das ist immerhin die Beschreibung von Turingmaschinen, auf die Tibor Radó (zumindest seine Fleißige Biber) aufgesetzt hat. Kleene schreibt da (soweit wie ich das auf die Schnelle gepeilt habe) von „active situations“ und „passive situations“, wobei letztere Halt-/Endzustände sind. Sowas wie „accepted“ und „non-accepted“ habe ich nicht gefunden. Verwürfelt der Artikel hier also etwas? VG --Apraphul ^Disk 19:21, 19. Jan. 2016 (CET)

Habe den Text im Artikel nochmal nachgelesen... ja, kann sein, daß ich dran vorbei geredet habe. Es gibt nicht nur eine Möglichkeit zu modellieren. Im Artikel ist offenbar doch eine andere gemeint, als ich erst verstanden habe: man benutzt mehrere Endzustände, und hängt diesen das zusätzliche Attribut „akzeptierend“ oder „nicht akzeptierend“ an. Wenn die TM dann hält, entscheidet das Attribut des Endzustandes. Das ist ok, das kann man so machen. Mir ist das nicht geläufig, und habe noch keine Formalisierung davon gesehen, weswegen ich erstmal „dran vorbei“ war. Eine Referenz wäre gut, wo es so gemacht wird; vielleicht läßt sich auch der Text verbessern, ohne ihn wesentlich zu verlängern. Aber der „$q_{f}\in Q$ ist der akzeptierende Zustand“ ist jedenfalls ein Endzustand (einer der hält). Und wenn man die Unterscheidung „akzeptierend“ oder „nicht akzeptierend“ am Ende auf dem Band kodiert hat, braucht man auch nur den einen. Hier ist „akzeptierend“ im Sinne dieser anderen Modellierung gemeint. Eine unglückliche Wortwahl, weil sie eines von mehreren möglichen Modellen vorraussetzt. Das sollte geändert werden. --H.Marxen (Diskussion) 20:11, 19. Jan. 2016 (CET)

Mir ist das leider etwas zu hoch. Helfen diese Links dem Verständnis? Dokument mit Vorkommen von "akzeptierender/verwerfender Endzustand", Dokument über "Akzeptierende Turingmaschine" und Wikiartikel "Alternierende Turingmaschine". VG --Apraphul ^Disk 20:33, 19. Jan. 2016 (CET)

• Der Artikel Alternierende Turingmaschine hilft mir hier gar nicht.
• Das erste PDF zeigt, wie man eine TM benutzt, um ein Wort einer Sprache zu akzeptieren, mit zwei Endzuständen q- und q+.
• Das zweite PDF macht etwas ähnliches, aber erst mal mit vielen akzeptierenden Endzuständen, von denen dann gezeigt wird, daß man sie weg-normieren kann, so daß genau ein akzeptierender Endzustand bleibt (der dort Stopzustand heißt).

Also zweimal die im Artikel oben intendierte Modellierung des Wortproblemes. --H.Marxen (Diskussion) 21:07, 19. Jan. 2016 (CET)

Ist doch grad egal was man schreibt, da sich die Maschinen sehr leicht ineinander überführen lassen. --95.115.8.199 21:13, 21. Jan. 2016 (CET)

Beispiel uneinheitlich!?

Im Turingmaschine#Beispiel wird mal die Folge 1110... => 1110111 und mal die Folge 110.. => 11011 als Beispiel angeführt. Das ist leider - gerade als Beispiel (sic!) - irreführend. Bitte mal vereinheitlichen. Danke. --91.66.44.153 10:11, 5. Jan. 2017 (CET)

Du hast nicht so ganz unrecht, aber es sind andererseits ja auch zwei (nicht eines) getrennte (Eingabe-)Beispiele für dieselbe Maschine. Du unterstellst jetzt automatisch, dass die Aussage über das erste Beispiel mit den drei Einsen auch im unteren Beispiel mit der Schrittfolge dargestellt werden sollte. :-) Das wären aber recht viele Schritte (und nicht "nur" 16 Schritte wie bei zwei Einsen), was den verhältnismäßigen Rahmen einer Schrittfolgendarstellung wohl sprengen würde. Aber man kann's ja anders herum anpassen. Ich schaue mal ... VG --Apraphul ^Disk _WP:SNZ 11:48, 5. Jan. 2017 (CET)

Gemacht. --Apraphul ^Disk _WP:SNZ 11:57, 5. Jan. 2017 (CET)