Diskussion:Automat (Informatik)/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:Automat (Informatik)/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Automat_(Informatik)/Archiv/1#Thema_1

Moore- und Mealy-Automaten

Sollte man nicht noch Moore- und Mealy-Automaten erwähnen, die nicht Akzeptoren (Wörter akzeptierende Automaten), sondern Transduktoren (die ein Wort in ein anderes übersetzen) sind? Roffle 08:33, 12. Apr 2005 (CEST)

imho ja... und natürlich als Spezialfall auch den Medwedew-Automaten. Ich bin sogar sehr erstaunt, dass sich diese Automaten hier nicht finden, da sie für den Entwurf digitaler Schaltungen die elementare Basis sind. Und was wäre die Informatik ohne digitale Schaltungen? ;-) --Ruscsi 22:13, 14. Aug 2005 (CEST)

Ich muss auch sagen, dass mir diese Seite deutlich zu phänomenologisch und unvollständig an die Sache herangeht. Es fehlt einerseits eine klare Definition und eine vernünftige Abgrenzung, andererseits wird nicht (wie oben bereits erwähnt) auf die Grundautomatentypen eingegangen. Die Digitaltechnik ist im übrigen nur ein angewandter Bereich, die Grundautomatentypen sind jedoch mathematische Modelle (=Beschreibungen) und somit viel allgemeinerer Natur. Ich kann einen solchen Automaten auch aus Konservendosen oder Zahnrädern bauen, ich könnte sogar ein natürliches System finden, welches den selben Gesetzen gehorcht, wichtig sind die Eigenschaften als solche. Eine Abgrenzung eines Automaten zu einem Vektor (z.B. digitales Netzwerk) ist z.B. der Besitz eines Zustandsspeichers, eine NOTWENDIGE eigenschaft jedes Automaten. MV --84.167.169.44 12:35, 16. Nov 2005 (CET)

Neuronales Netz ein Automat?

In welchem Sinne ist denn ein neuronales Netz ein Automat, so wie es die theoretische Informatik versteht? Diesem Artikel fehlt ja leider eine wirkliche Definition des Begriffs, aber normalerweise versteht man ja unter Automaten auf jeden Fall ein Konstrukt mit diskreten Zuständen. Eine grundlegende Eigenschaft neuronaler Netze ist ja aber gerade die Verwendung kontinuierlicher Aktivitäten (dass diese als normalerweise mit Hilfe von digitalen Rechnern simuliert werden ist wieder eine andere Sache...), sie lassen sich daher nicht wie Turingmaschinen etc. beschreiben. Also, habe den Verweis rausgenommen, Gruß --eo !? 20:16, 22. Okt 2005 (CEST)

Öh, bitte? (künstliche) neuronale Netze, wie sie in der Informatik verwndet werden, haben diskrete Zusände: jedes Neuron kann diskrete "Ladungen" (Zusände) annehmen, die "Berechnung" erfolgt in diskreten Schritten, meist parallel an allen Neuronen. Ansätze zu (künstlichen) analogen Netzen gibt es bestimmt, das ist aber sicher nicht der Normalfall. Gemäss der Church-Turing-These wäre ein solches aber auch nicht grundsätzlich mächtiger, als ein digitales, d.h. es könnte digital simuliert werden, wenn auch u.U. mit erheblichem Aufwand.

Ich hab' den Link erstmal wieder in den Artikel aufgenommen - diesmal aber präzieser auf Künstliches neuronales Netz-- D. Dÿsentrieb ⇌ 13:53, 16. Nov 2005 (CET)

Dass die Berechnungen in diskreten Schritten ablaufen, ist natürlich trivialerweise richtig, da die Netze ja meist auf digitalen Rechnern simuliert werden. Einige einfache Modelle (z.B. McCulloch-Pitts-Zelle) verwenden auch diskrete (meist binäre) Zustände und bei so einem Netz könnte man wohl von einem Automat sprechen (war ja auch die Intention von McCulloch/Pitts). Normalerweise versteht man (ich?) aber unter einem Künstlichen Neuronalen Netz doch etwas wie ein Multilagenperzeptron, wo die einzelnen Neuronen als Aktivität einfach eine reelle Zahl (im Digitalrechner wird die natürlich wieder diskret) als Analogon zu der Spikerate einer Nervenzelle haben. Solche Netze gehören in den mathematischen Bereich der Statistik (Funktionsapproximation) und nicht in den der diskreten Mathematik, wo ich die theoretische Informatik jetzt einfach mal dazu zähle. Kennst Du denn z.B. ein Lehrbuch, in dem Neuronale Netze als Automaten bezeichnet werden? Gruß eo !? 17:14, 16. Nov 2005 (CET)

Puh, Leerbücher sollten 'ne Suchfunktion haben ;) In bezug auf reelle Zahlen hast du recht, das kommt wohl in einigen Modellen vor. Ob die Möglichkeit, reelle Zahlen zu speichern und zu verarbeiten, die Definition eines Automaten im Sinne der Automatentheorie sprengt, ist interessant... die Berechnungsmächtigkeit dürfte nicht über der einer Turingmaschine liegen, sonst wäre die Church-Turing-These widerlegt, oder? Algorithmen können zumindest durchaus auf reellen Zahlen arbeiten, die Theoretische Info lässt sich nicht auf die DM beschränken.

Für mich hat ein neuronales Netz zu jedem Zeitpunkt einen wohldefinierten Zustand, und der Folgezustand ist durch die Eigenschaften des netzes eindeutig definiert. Bzw., im nichtdeterministischen Fall, die Menge der möglichen Folgezusände. Das macht es für mich erstmal zu einem Automaten: das Ding folgt einem Algorithmus. Man müsste sich jetzt fragen, ob Endzustände auch notwendig sind, ob ob's sowas für alle Arten von NN gibt, also wie's um die terminiertheit bestellt ist.

Was hältst du davon, NN als "verwandtes Konzept" zu erwähnen, statt sie direkt als Automaten aufzuführen? Ob sie wirklich welche sind, hängt wohl von einer allgemeinen Definition für "Automat" ab - die in dem Artikel leider fehlt. Und ich könnte mir jetzt auch nur eine aus den Fingern saugen, ich kenne saubere Definitionen nur für die einzelnen Arten von Automaten, keine allgemeine. -- D. Dÿsentrieb ⇌ 18:02, 16. Nov 2005 (CET)

Manche Lehrbücher haben immerhin einen Index ;-) Ich wollte gar nicht argumentieren, dass NNs berechnungsmächtiger wären (auch wenn das eine interessante philosophische Debatte ist, wenn man es auf natürliche Netze bezieht) nur ist mein Begriff eines Automaten wohl einfach enger gefasst. Wenn man aber Automat=Algorithmus setzt, dann gehören ja noch viel mehr Konzepte zu den Automaten... Ich würde also dafür plädieren, den Begriff Automat (Informatik) relativ eng zu fassen und nur die "klassischen" Automaten (also alle Formen von Turingmaschinen mit Varianten wie Zelluläre Automaten + die in der obigen Diskussion erwähnten Mealy-Automaten etc.) aufzuführen. Würde der Artikel Berechnungsmodelle heißen, dann wäre das was anderes... Nebenbei bemerkt, was hälst Du davon diesen relativ umfangreichen Artikel mit dem eher dürftigen Automatentheorie-Artikel zu verschmelzen? Gruß --eo !? 18:49, 16. Nov 2005 (CET)

Für mich ist ein Automat das gleiche wie ein Berechnungsmodell, obwohl ich diesen Begriff etwas unscharf finde. Automaten und Algorithmen sind jedoch völlig unterschiedlich: ein Automat ist (wenn er terminiert) eine Implementation eines Algorithmus. Der selbe algorithmus kann in unterschiedlichen Automaten-Modellen umgesetzt werden, mit verschiedenen Ergebnissen für die Platz/Zeitkomplexität.

Automatentheorie mit Automat (Informatik) zusammenzulegen finde ich keine so gute idee - Automatentheorie is halt eine Schnittpunkt von Berechenbarkeitstheorie, Komplexitätstheorie und Formalen Sprachen, der sich mit Automaten beschäftigt. Man kännte einfach alles in Automatentheorie einbauen, aber die Infos, die jetzt hier sind, passen schon besser unter das Lemma Automat. Unter Automatentheorie sollte vermutlich was über entwicklung und geschichte stehen - eine zusammenlegung der Artikel würde einer solchen Erweiterung im Weg stehen.

Die Aussage über Moore- und Mealy-Automaten oben halte ich für schlicht falsch - nach allem, was ich gelernt habe, sind das zwei (fast) äquivalente Arten, Endliche Automaten zu denfinieren. EAs, die eine Ausgabe erzeugen, lassen sich sicher definieren, sind mir aber nicht geläufig. In bezug auf die Theoretische Informatik tun das eigentlich nur manche Turing-Maschinen.

Also, was machen wir jetzt mit den Neuronalen Netzen? Oder besser: woher bekommen wir jetzt eine brauchbare, allgemeine definition von "Automat"? Mir fällt gerade auf, dass ich mich schon echt lange mit Automaten befassen, aber über eine präziese, allgemeine Definition hab' ich mir nie Gedanken gemacht. -- D. Dÿsentrieb ⇌ 22:42, 16. Nov 2005 (CET)

Also, in aller Kürze:

• Zur Automatentheorie: Wenn da was über Geschichte und Entwicklung stehen würde, ok. Bin nur darüber gestolpert, dass im Artikel eigentlich nur steht "Automatentheorie beschäftigt sich mit Automaten"...
• Welche Aussagen über die Automaten hälst Du denn für falsch? Mealy- und Moore-Automaten sind zwar in einem gewissen Sinn zu endlichen Automaten äquivalent (fehlt natürlich auch in den jeweiligen Artikeln...), sind aber immer so definiert, dass sie eine Ausgabe erzeugen. In meinem Studium spielten die zwar nie eine Rolle, sind aber so weit ich weiß für eher "praktische" Modellierungsaufgaben durchaus relevant und verbreitet.
• Neuronale Netze: Tja, es hängt wohl alles an der Definition... Die einzige, die mir auf die Schnelle einfällt: Ein Automat besteht aus Programm (Zustandsüberführungen), Zustand und Speicher (Bänder). Damit hat man natürlich alles von endlichen Automaten bis Turingmaschinen eingeschlossen, aber auch Petri-Netze, zelluläre Automaten etc. (die, nebenbei bemerkt, in dem einzigen mir gerade vorliegendem Lehrbuch als Automatennetze bezeichnet werden). Neuronale Netze würde man zumindest nie in dieser Form definieren...

Also, ich gebe zu, Du hast gute Argumente, warum man neuronale Netze (ganz besonders solche mit binären Neuronen) auch als Automaten bezeichnen könnte. Mein Problem damit resultiert daraus, dass in meinem Studium der Begriff Automat sehr eingeschränkt gebraucht wurde, nämlich nur für endliche Automaten, schon Turingmaschinen waren keine Automaten sondern Maschinen. Um alles unter einen Hut zu bringen (z.B. auch, das noch gar nicht mit einem Artikel gewürdigte Konzept der Schaltkreise als Modell der theoretischen Informatik), handelte die Vorlesung zu dem Thema auch von Berechnungsmodellen. Da ja aber meine persönliche Erfahrung nicht maßgeblich ist, generell gefragt: Würden in einer Uni-Veranstaltung oder in einem Lehrbuch mit dem Thema "Automaten", die neuronalen Netze eine Rolle spielen? Ich denke nicht. Aber, (viel zu) lange Rede, kurzer Sinn: Mit Deinem Kompromiss-Vorschlag "verwandte Konzepte" (oder vielleicht: "andere Berechnungsmodelle") könnte ich leben :-) Gruß --eo !? 10:45, 17. Nov 2005 (CET)

Jo, das klingt ja alles schonmal ganz gut :) Also...

• Die Automatentheorie muss dringend überarbeitet werden. Eine zusammenlegung würde das aber mMn eher verhindern. Leider kenne ich mich mit der Geschichte zu wenig aus, um dazu was zu schreiben.
• Ich hab' mich geirrt, was Moore- und Mealy-Automaten angeht, du hast völlig recht. Sie definieren eine Ausgabe. Wird wohl echt so selten verwendet, dass ich es vergessen habe.
• Zellulären Automaten hiessen nicht umsonst so ;) Sie werden nach meiner Erfahrung formal auch genau so behandelt wie andere Automaten (gleiche Formalismen, Eigenschaftem) - der grösste Unterschied zu "normalen" Automaten besteht wohl darin, dass sie keinen globalen Zustandsspeicher haben, dafür aber ein mehrdimensionales "Band".
• Einen Unterschied zwischen "Automat" und "Maschine" kenne ich nicht, scheint mir künstlich bzw. historisch bedingt zu sein. Z.B. spicht der Hopcroft/Ulman von Moore- und Mealy-Maschinen; Und linear begrenzte Turingmaschinen heissen linear bounded automaton (LBA).
• Petrinetze und Neuronale Netze werden traditionell nicht als Automaten beszeichnet, da hast du wohl recht. Ich sehe aber Formal keine scharfe Abgrenzung - insb. kann ein Petrinetz mit kleinen Erweiterungen (Sperrkanten reichen, glaube ich) eine Turingmaschine simulieren. Das müsste man wohl irgendwie in den Artikel einbringen. Es fehlt wirklich an einer brauchbaren Definition für "Automat"...

Gruss, -- D. Dÿsentrieb ⇌ 15:08, 17. Nov 2005 (CET)

Nachtrag: Ich hab' nach kurzer Suche das hier gefunden: Arto Salomaa, Derick Wood, Sheng Yu (Ed.): A half century of automata theory ISBN 981-02-4590-4; Wer Lust und Zeit hat, könnte sich das ja mal angucken und die Automatentheorie überarbeiten. -- D. Dÿsentrieb ⇌ 15:23, 17. Nov 2005 (CET)

einfache Sprache gefordert

Liebe Wikinger, seid bitte sprachlich etwas genauer, denn Formalismen wie geklammerte Wörter helfen uns allen nicht weiter. Es gibt bestimmt in der natürlichen Sprache einen Ausdruck für Automat(Informatik), etwa "digitaler Automat". Das wäre dann auch für Normaldenker verständlicher. Auch ist hier zwischen der Idee bzw. dem Modell, dem Automatenmodell, und der Verwirklichung eines Automatenmodelles (Maschine?) zu unterscheiden. G --Jens611 10:29, 14. Mär. 2008 (CET)

Ich verstehe das Problem nicht ganz. Meiner Meinung nach unterscheiden sich die beiden Artikel Automat (Informatik) und Automatenmodell thematisch überhaupt nicht voneinander. In beiden Fällen handelt es sich sowohl um das theoretische Modell aus dem Berech der Informatik, in dem Artikel Automat (Informatik) wird zusätzlich gesagt, dass sich dieses Modell auch für die Praxis umsetzen lässt, z.B. beim Compilerbau. Im Artikel Automatenmodell werden nur die Endlichen Automaten, Kellerautomaten und Turingmaschinen erwähnt. Damit sind in der Chomsky-Hierarchie aber nur die Sprachklassen 0,2 und 3 abgedeckt. Der Artikel ist daher unvollständig, weil z.B. die linear beschränkten Automaten für die kontextsensitiven Sprachen fehlt. Ebenso wird erwähnt, dass es dazu eine deterministische und nicht-deterministische Variante dieser 3 Typen gibt, ohne exakt zu klären, was Nichtdeterminismus im Bezug auf Automaten bedeutet (z.B. P versus NP).

Ich denke, man sollte beide Artikel zusammen führen. Über den Namen kann man danach immer noch streiten. Als Informatiker würde ich nicht nach "digitalen Automaten" suchen, weil bei uns an der Uni wird immer nur von Automaten geredet. Meinetwegen kann man den Artikel auch Automatentheorie nennen, aber es ist echt unvorteilhaft, dass es 2 Artikel zum selben Thema gibt. --Freaky86 12:16, 14. Mär. 2008 (CET)

Für ein anderes Lemma käme soweit ich das sehe nur "Abstrakte Maschine" in Frage, aber da "Automat" im Deutschen wohl klar die gebräuchlichere Bezeichnung ist, halte ich "Automat" für die treffendere Variante, aufgrund der Mehrfachverwendung des Begriffs entsprechend der Wikipedia-Konventionen als Klammerlemma. Was für Probleme "Normaldenker" damit haben könnten, ist mir schleierhaft.

Unabhängig davon ist mir immer noch nicht klar, wie du Modell und Verwirklichung (?!?) unterscheiden willst, und vor allem in wie weit der getrennte Automatenmodell-Artikel dieser Unterscheidung gerecht werden soll (es gibt ja immerhin noch einen Artikel Automatentheorie zum Wissenschaftszweig). Jens611, erkläre doch bitte endlich mal, worin sich dein Artikel von diesem hier unterscheidet, warum man ihn also brauchen sollte, und was man bei einer Zusammenlegung ggf. hier her übernehmen sollte (ich sehe nichts). --YMS (Diskussion) 16:34, 15. Mär. 2008 (CET)

Hallo. Habe mal den Artikel überarbeitet und strukturiert.--AlfonsGeser 23:22, 14. Mai 2008 (CEST)

Ungültiges Archivierungsziel

Die Zielangabe bei der automatischen Archivierung dieser Seite ist ungültig. Sie muss mit demselben Namen wie diese Seite beginnen. Wende dich bitte an meinen Besitzer, wenn das ein Problem darstellen sollte. ArchivBot 03:41, 24. Aug. 2011 (CEST)

erledigtErledigt Harry8 08:55, 24. Aug. 2011 (CEST)