Formale Systeme, Axiome und Sätze

[Ines]

Hallo Juser.

Ich gebe dem Thread erstmal keine lange Lebensdauer, da das Thema doch recht speziell ist.

Ich möchte aber doch kurz meinen Gedankengang versuchen darzulegen.
Gestern las ich mal wieder in Hofstadters "Gödel, Escher, Bach" das Kapitel über formale Systeme , genauer das MIU-System. Die Links geben ein paar Hinweise für Unbeleckte.

Grob verkürzt kann man mit so einem einfachen formalen System Zeichenketten erzeugen, und zwar nach gewissen Regeln, z.B: Wenn wir annehmen, daß unser Alphabet nur aus den Buchstaben MIU besteht, dann wären denkbare Ketten MUII, MIUMUM oder MIU. Kombinationen halt.

Eine Regel wäre: Wenn man eine Kette besitzt, deren letzter Buchstabe I ist, kann man am Ende ein U anfügen. Oder: Wenn in der Kette die Folge III vorkommt, darf man diese III durch ein U ersetzen oder: Wenn man Mx hat (wobei x eine beliebige Folge ist), dann darf man x anhängen...usw.

Eine Startzeichenkette, mit der man also beginnt, nennt man ein Axiom (=kostenloser Satz ) und die daraus durch die Regeln erzeugten Ketten nennt man Sätze.

Die Ableitung eines Satzes bedeutet hier, anzugeben, welche Regeln wann angewandt wurden, um die Kette zu erzeugen, z.B: 1) MI 2) MII (aus 1 mit Regel 3) 3) MUIUI (aus 2 mit Regel 5) etc.

Nun kann man sich also Regeln zurecht legen und damit munter Zeichenketten erzeugen..je nach verwendeten Symbolen und Regeln. Man kann ja ein bisschen herumexperimentieren. Nach einer Weile wird sich herauskristallisieren, daß bestimmte Kombinationen von Zeichen nie auftauchen werden, bzw. bestimmte Zeichen nie die Kette verlassen werden, eben aufgrund der festgelegten Regeln.

Hofstadter führt im Buch an, daß ein intelligentes Wesen diesen Umstand irgendwann erkennen werde, eine Maschine jedoch ewig weitererzeugen würde, ohne eine Gesetzmäßigkeit zu erkennen.

Darauf will ich aber nicht hinaus. Da es sich in dem Buch oft um Kreisschlüsse und seltsame Schleifen dreht, kam mir die Frage in den Sinn, die ich auch an euch stellen werde (obwohl ich nicht viele Antworten erhoffe ):

Wie muß ein formales System beschaffen sein bzw. welche Regeln müssen gelten, damit folgender Wunsch von mir erfüllt ist: Die auf irgendeinem Wege erzeugte Zeichenkette gibt durch die Reihenfolge ihrer Zeichen an, welche Regel wann angewendet wurde, sie codiert also praktisch teilweise ihre Ableitung in sich selbst und zwar so daß man weiß, welche Regel wann angewandt wurde, aber nicht was diese Regel besagt.

Genauer: Jeder Buchstabe des verwendeten Alphabets soll genau einer angewendeten Regel zugeordnet sein ( I = Regel 1 oder U = Regel 3) und jede erzeugte Kette des Systems soll also diese Information erhalten.

Bsp: Kette MUIIMU soll gleichzeitig aussagen: 1. Buchstabe = M soll bedeuten zuerst Regel M (oder meinetwegen auch eine Ordnungszahl, falls man die Regeln gern numerieren möchte) angewendet, auf die daraus folgende Kette dann U, auf diese Kette dann Regel "I" zweimal. usw. usw.

Wahrscheinlich gibt es dafür eine triviale Lösung, so wie ich mich und meine Ideen kenne. Ich komm aber nicht drauf.

Also welche Regeln müssen gelten, damit diese Selbstcodierungsbedingung erfüllt ist? Oder ist so etwas gar nicht möglich?

EDIT: Und kann man so möglicherweise so sogar auf den genauen Regelinhalt schließen und ab wann ist dies möglich?


PS: Hoffentlich überfordere ich niemanden. Hoffentlich ist das überhaupt richtig in der DE..

[Polly]

Ich weiß nicht, in wie weit du in der theoretischen Information bewandert bist, aber du solltest dich mal über formale Sprachen, formale Grammatiken und eventuell noch die Kleenesche Hülle informieren. Du sprichst hier zwar von formalen Systemen, diskutierst aber über die spezielleren formalen Grammatiken.

Ich bin mir nicht sicher, ob ich dein Problem verstehe, aber du möchtest anscheinend eine Zeichenkette erzeugen, deren grammatikalischer Ursprung in der Zeichenkette selbst codiert ist. Spontan würde ich dir empfehlen dich mal über reguläre Sprachen, endliche Automaten und die Chomsky-Hierarchie zu informieren.

Da du offensichtlich die zeitliche Abfolge der Regeln in die Zeichenkette codieren willst, müsstest du mit Grammatiken arbeiten, die die Zeichenkette jeweils nur links oder rechts fortsetzen, da ansonsten die Reihenfolge der Regeländerungen verloren gehen würde. Nun könntest du jeder Regel ein anderes Terminalsymbol zuordnen, welches durch die anderen Regeln nicht mehr verändert werden kann und damit genau angibt, welche Regel zu welchem Zeitpunkt angewendet wurde. Ich fürchte allerdings, dass das Thema etwas zu komplex ist, um es ausgiebig über ein Forum zu diskutieren.

[Polly]

Habe ich "theoretische Information" geschrieben?

Ich meinte natürlich "theoretische Informatik".