aus Wikipedia, der freien Enzyklopädie

Hallo,

zu folgenden Seiten freue ich mich über Stellungnahmen: Am besten Ihr tragt Eure Bemerkungen direkt unter dem Titel auf dieser Seite ein!

--Gerhard Buntrock 16:07, 14. Aug 2005 (CEST)

Inhaltsverzeichnis 1 Komplexitätstheorie 1.1 3COLOR 1.2 Akzeptieren 1.3 Logarithmisch platzbeschränkte Reduktion 1.4 LOGCFL (Komplexitätsklasse) 1.5 NTIME 1.6 NP (Komplexitätsklasse) 1.7 P (Komplexitätsklasse) 1.8 Reduktion (Theoretische Informatik) 1.9 Satz von Cook 1.10 Quasi Realzeit-Sprache 2 Formale Sprachen und Automatentheorie 2.1 Alphabet (Informatik) 2.2 Büchi-Automat 2.3 Formale Grammatik 2.4 Formale Sprache 2.5 Deterministisch kontextfreie Sprache 2.6 Konfluenz (Informatik) 2.7 Kontextfreie Sprache 2.8 Lineare Sprache 2.9 Morsefolge 2.10 Reguläre Sprache 2.11 Semi-Thue System 2.12 Wortproblem 2.13 Zweikellerautomat 3 Rekursionstheorie 3.1 Aufzählbarkeit 3.2 Berechenbarkeit 3.3 Church-Turing-These 3.4 Diophantische Gleichung 3.5 Fleißiger Biber 3.6 Gödelscher Unvollständigkeitssatz 3.7 Rekursive Aufzählbarkeit 3.8 Unentscheidbarkeit 4 Logik 4.1 Gödelscher Unvollständigkeitssatz 4.2 Natürliche Zahl 4.3 Theorie 5 Sonstiges 5.1 Dualsystem 5.2 Gen 5.3 Involution (Mathematik) 5.4 Julius Richard Büchi 5.5 Kybernetik 5.6 Quersumme 5.7 ReiserFS 5.8 Ronald V. Book 5.9 Schmetterlinge 6 Kritik rein formaler Natur 6.1 Semi-entscheidbare Menge vs. Semi entscheidbare Menge 6.2 Sheila A. Greibach 6.3 Kategorientheorie und Wikipedia-Kategorien 6.4 Emil Leon Post 6.5 Involution (Mathematik)

[Bearbeiten] Komplexitätstheorie

[Bearbeiten] 3COLOR

[Bearbeiten] Akzeptieren

[Bearbeiten] Logarithmisch platzbeschränkte Reduktion

[Bearbeiten] LOGCFL (Komplexitätsklasse)

[Bearbeiten] NTIME

[Bearbeiten] NP (Komplexitätsklasse)

[Bearbeiten] P (Komplexitätsklasse)

[Bearbeiten] Reduktion (Theoretische Informatik)

[Bearbeiten] Satz von Cook

[Bearbeiten] Quasi Realzeit-Sprache

[Bearbeiten] Formale Sprachen und Automatentheorie

[Bearbeiten] Alphabet (Informatik)

[Bearbeiten] Büchi-Automat

[Bearbeiten] Formale Grammatik

[Bearbeiten] Formale Sprache

[Bearbeiten] Deterministisch kontextfreie Sprache

Deine Artikel und Ergänzungen haben mir gefallen und da dachte ich, dass ich einmal etwas zu Deinem Gebiet beitrage. Habe oben genannten Artikel in einer Grundfassung erstellt. --Rtc 21:06, 26. Aug 2005 (CEST)

---

Vielen Dank! Hier sollten einige Abschnitte ergänzt werden: Beispiele, Eigenschaften, Verhältnis zu anderen Klassen, vielleicht auch Entscheidbarkeitseigenschaften... In der Literatur ist der Knuth etwas unvollständig weggekommen. --Gerhard Buntrock 03:24, 27. Aug 2005 (CEST)

---

Ok, habs ein bisschen vervollständigt. Es handelt sich um eine sehr praxisbezogene Sprachklasse, bei der wohl das größte Augenmerk auf die praktische Umsetzung fällt, den LR-Parser. Dort ist bereits ein ausführliches Beispiel einer deterministisch kontextfreien Sprache angegeben, sogar in Form einer Grammatik, welche die LR-Eigenschaft besitzt und den dazugehörigen Parser. Ich halte deshalb in diesem Artikel kein eigenes für notwendig. Im Text sind nun zwei Verweise auf S- bzw. LR-attributierte Grammatiken drin. So habe ich jedenfalls 'S-' bzw. 'LR-attributed grammar' übersetzt. Klingt irgendwie ein wenig holprig. Kennst Du vielleicht Begriffe dafür, die sich besser anhören oder sogar schon gängig sind? --Rtc 00:46, 7. Sep 2005 (CEST)

Sehr schön, ich habe jetzt noch einige Theorieresultate ergänzt. --Gerhard Buntrock 01:34, 9. Sep 2005 (CEST)

[Bearbeiten] Konfluenz (Informatik)

[Bearbeiten] Kontextfreie Sprache

[Bearbeiten] Lineare Sprache

[Bearbeiten] Morsefolge

[Bearbeiten] Reguläre Sprache

[Bearbeiten] Semi-Thue System

Wollte mich nur mal für deine umfangreichen Änderungen bedanken, gute Arbeit. --mGla 08:14, 26. Aug 2005 (CEST)

---

Es gibt soviel zu tun bei Wiki! Ich würde gerne noch mehr tun, aber meine ToDo -Liste wird immer länger! --Gerhard Buntrock 03:24, 27. Aug 2005 (CEST)

[Bearbeiten] Wortproblem

[Bearbeiten] Zweikellerautomat

[Bearbeiten] Rekursionstheorie

[Bearbeiten] Aufzählbarkeit

[Bearbeiten] Berechenbarkeit

[Bearbeiten] Church-Turing-These

[Bearbeiten] Diophantische Gleichung

[Bearbeiten] Fleißiger Biber

Weitreichende Änderungen durchgeführt. Bitte Gegenprüfen. --Rtc 05:00, 7. Sep 2005 (CEST)

Sehr schöner ARtikel, aber leider fehlerhaft. Da ich zur Zeit sehr busy bin, kann ich mich nicht drum kümmern. Daher hier nur kurz:

Die Σ Funktion ist eine Verallgemeinerung der σ-Funktion! Der Busy Beaver bezieht sich auf Σ! Der Unterschied besteht darin, dass Rado verlangt, dass zwischen den Einsen keine Nullen stehen dürfen. Beim BusyBeaver ist das aber erlaubt! Daher gilt stets: Gruß --Gerhard Buntrock 01:34, 9. Sep 2005 (CEST)

Du könntest recht haben. Ich schaue nochmal genau im Turing-Omnibus, welche Darstellung dort vorgenommen wird. Auch meine Anmerkung bezüglich des 4098er-Biber ist ggfs. falsch. --Rtc 18:48, 12. Sep 2005 (CEST)

Ich weiß nicht, was im Turing-Omnibus steht. Auf jeden Fall weiß ich, wie die Ausgabe der 4098 Strich-Maschine aussieht. Ich kann Dir gerne das Programm zukommen lassen. Vielleicht sollten wir es eh hier darstellen. Auf alle Fälle darf nicht σ und Σ durcheinandergewurstelt werden!

Viele Grüße und vielen Dank auch für Deinen Einsatz viele der von mir erstellten Seiten betreffend! --Gerhard Buntrock 07:56, 13. Sep 2005 (CEST)

Genau das meinte ich doch. Ich hatte die 4098er-Maschine sogar selbst auch einmal programmiert, und aus irgendeinem unerfindlichen Grund hatte ich die falsche Erinnerung, die ausgegebenen Einsen seien an einem Stück. Ein rauskramen aus dem Archiv und starten brachte dann allerdings schnell die Erkenntnis eines Irrtums. Ich habe auch heute konkret im Turing-Omnibus nachgeschaut. Dort ist in der Tat nur von Σ(n) die Rede. Ich kann mir immer Bilder sehr gut merken, und vermutlich entstand mein Missverstänis dadurch, dass das einzige Bild in dem Kapitel einen kleinen Biber auf dem Turingband zeigt, der an eine Kette von einsen eine weitere anhängt. Sorry für den kleinen Faux-Pas. --Rtc 19:08, 13. Sep 2005 (CEST)

[Bearbeiten] Gödelscher Unvollständigkeitssatz

[Bearbeiten] Rekursive Aufzählbarkeit

[Bearbeiten] Unentscheidbarkeit

[Bearbeiten] Logik

[Bearbeiten] Gödelscher Unvollständigkeitssatz

[Bearbeiten] Natürliche Zahl

In der Definition endlicher Mengen fehlt das Äquivalent des fünften Peano-Axioms. Wieso kann man nicht einfach alle Mengen endlich nennen? Die Forderungen sind dann erfüllt.--Gunther 11:56, 24. Aug 2005 (CEST)

---

Endlich fällt nicht vom Himmel. Da man es exakt definieren kann, habe ich es nachgetragen. Ich hoffe, es bleiben meine Ziele sichtbar: Der Zahlbegriff ist jedem natürlich vertraut, wir machen uns den Prozess der Äquivalenzklassenbildung und eines Repräsentantensystems nur gar nicht mehr bewusst. So gibt es Kulturen, in denen fehlen die Wörter für große Zahlen. Dennoch weiß man, dass sie sich einen Begriff von großen Zahlen machen. Den machen sie immer mit der Methode genausoviel wie: Z.B. Ich habe jetzt soviel Brennholzstücken wie Mitglieder in meinem Stamm. Oder: Ich habe jetzt soviel Stücken, dass jeder 12 Stück bekommen kann, 5 bleiben übrig.
Gruß --Gerhard Buntrock 03:24, 27. Aug 2005 (CEST)

Die im Text gegebene Definition endlicher Mengen ist aus heutiger Sicht unpräzise. Induktive Definitionen zu präzisieren ist meist auf zwei Arten möglich: Entweder "von unten", d.h. "es gibt eine Folge , so dass X_{n + 1} aus X_n durch Hinzufügen eines Elementes entsteht", oder "von oben", d.h. "die Menge der endlichen Mengen ist die kleinste Menge von Mengen, die (a) die leere Menge und (b) zu jeder Menge jede um ein Element vergrößerte Menge enthält." Die erste Möglichkeit funktioniert nicht, weil sie natürliche Zahlen voraussetzt, die zweite, weil es um echte Klassen geht und man für sie keinen Allquantor hat.--Gunther 10:24, 27. Aug 2005 (CEST)

---

Also ich habe mich jetzt damit noch einmal auseinandergesetzt und muss sagen, dass meine Vorstellung, die mir bewusst war, als ich in dem Artikel editierte, doch einige Trübungen in den letzten Jahren erlitten hat! So muss ich mich bedanken, dass mir hier verschiedene Dinge wieder von Neuem deutlich geworden sind. Insbesondere der Einwurf das Russel den Begriff der Menge in seiner Definition verlässt!

Ebenso der Hinweis, dass die Schwäche nur im Fall der ersten Stufe gilt. Hier wird dann das Induktionsaxiom zur Menge von Axiomen (es gibt hier auch andere Formen). Das hat mit Sicherheit hier keine so wichtige Bedeutung.

Schließlich freue ich mich, dass die Russellschen Vorstellungen, die dem Neuling sicher einen ersten Einblick in die mathematische Denkweise geben, drin geblieben ist.

Gruß --Gerhard Buntrock 01:34, 9. Sep 2005 (CEST)

---

[Bearbeiten] Theorie

[Bearbeiten] Sonstiges

[Bearbeiten] Dualsystem

Hier muss der Begriff dyadisches System nachgetragen werden und zum Teil korrigiert werden!

[Bearbeiten] Gen

[Bearbeiten] Involution (Mathematik)

[Bearbeiten] Julius Richard Büchi

[Bearbeiten] Kybernetik

[Bearbeiten] Quersumme

[Bearbeiten] ReiserFS

[Bearbeiten] Ronald V. Book

[Bearbeiten] Schmetterlinge

[Bearbeiten] Kritik rein formaler Natur

[Bearbeiten] Semi-entscheidbare Menge vs. Semi entscheidbare Menge

Vorhin habe ich den Artikel von Semi entscheidbare Menge unter das korrekte Lemma Semi-entscheidbare Menge verschoben. Bitte die neuen Inhalte dort unterbringen und danach mit {{Löschen}} die Schnellöschung des falschen Lemmas beantragen, danke.--Gunther 15:19, 26. Aug 2005 (CEST)

Hab das alte Lemma gelöscht, dankeschön.--Gunther 15:41, 26. Aug 2005 (CEST)

Ich bedanke mich für Deine Hilfestellung. So ein Bindestrichfehler ist mir jetzt schon das zweite Mal passiert!
Grüße --Gerhard Buntrock 03:24, 27. Aug 2005 (CEST)

[Bearbeiten] Sheila A. Greibach

Hiho, ich war übrigens bis vor zwei Jahren noch in Lübeck an der Seefahrtsschule, ich saß hinten in der Bibliothek. Einige Anmerkungen zu dem Artikel: ich hab mal einen Einleitungssatz geschrieben, direkt im ersten Satz sollte ansatzweise klar werden, wer diese Person ist. Ansonsten fehlt etwas zu ihrer Relevanz: Ist sie Professorin? Hat sie Bücher veröffentlicht? Hat sie ein wichtiges Problem gelöst? Bisher steht dazu noch nichts und so wäre der Artikel wegen mangelnder Relevanz löschgefährdet. Dann mal eine Anmerkung zu Deinem Seitenlayout auf dieser Seite: Die Diskussionen zu Artikeln finden ja meist auf der entsprechenden Diskussionsseite statt und viele finden es praktischer, ihre Sachen chronologischer zu ordnen. --DaTroll 11:02, 27. Aug 2005 (CEST)

Ich bin zunächst mal ganz zufrieden über den Erfolg meines Vorgehens. Viele Grüße! --Gerhard Buntrock 01:34, 9. Sep 2005 (CEST)

[Bearbeiten] Kategorientheorie und Wikipedia-Kategorien

Ich habe die Kategorie:Mathematik wieder herausgenommen, weil die Kategorie:Kategorientheorie in Kategorie:Mathematik enthalten ist. Außer in wirklichen Ausnahmefällen sollte ein Artikel immer nur in den jeweiligen "untersten" Kategorien einsortiert sein.--Gunther 12:37, 31. Aug 2005 (CEST)

Alles klar. Ich habe das so nicht vorgefunden und daher auch nicht danach gehandelt. Stimme dem inhaltlich auf alle Fälle zu! --Gerhard Buntrock 12:41, 31. Aug 2005 (CEST)

[Bearbeiten] Emil Leon Post

Hallo Herr Buntrock, wusste gar nicht, dass Sie auch für die Wikipedia schreiben. Wie schön! Qualifizierte Leute können hier bestimmt nicht schaden. Handelt es sich bei dem Emil Post in Ihrer ToDo-Liste um den vom Postschen Korrespondenzproblem? Falls ja, dazu gibt es bereits den in der Überschrift verlinkten Artikel. Nicht sehr ausführlich, aber immerhin ist ein Grundstock da. Grüße aus Lübeck! --Winne 21:27, 8. Sep 2005 (CEST)

In der Tat! Vielen Dank für den Hinweis!

Leider habe ich viel zu wenig Zeit, für das interessante Forum vom Wikipedia, das hier doch ein ganz beträchtliches Wissen zusammenträgt. Da ich gerne hier im verrauschten Lexikon nachschlage und immer wieder was zum Verbessern sehe, habe ich mir dann hier doch immer mal wieder etwas Zeit genommen. --Gerhard Buntrock 01:34, 9. Sep 2005 (CEST)

[Bearbeiten] Involution (Mathematik)

Wenn ich mich in der Versionsgeschichte nicht verklickt habe, hast Du mal die Einleitung zu diesem Artikel geschrieben. Leider ist die angegebene Etymologie in der Form falsch. "Flattern" heisst auf lateinisch involitare und nicht wie angegeben involutare. Dann müsste allerdings erklärt werden, weshalb es Involution und nicht Involition heisst. Ich bin sehr skeptisch, dass das Wort tatsächlich von involitare abgeleitet ist. Kannst Du eine Quelle dafür angeben? --Enlil2 22:27, 25. Dez. 2006 (CET)