Turbo Toolbox

home *** CD-ROM | disk | FTP | other *** search

/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 21 / artikel.asc < prev next >

Wrap

Text File | 1991-05-03 | 52.5 KB | 1,189 lines

Automaten und Sprachen der Informatik von Burkhard R. Wittek Komplexitätsstufen von Sprachen und Automaten zwischen Datenverarbei- tung und Künstlicher Intelligenz - zwischen FastFood der Automaten- theorie und der Kochkunst á la Bocuse der Künstlichen Intelligenz Der Ausdruck "Künstliche Intelligenz" oder englisch "artificial intel- ligence" ist inzwischen in aller Munde. Jedermann, der schon einmal einen Computer zu Gesicht bekommen hat, glaubt, darunter etwas zu ver- stehen oder gebraucht ihn, ohne einmal wirklich nachgefragt zu haben, was eigentlich damit gemeint ist. Weil die Beantwortung dieser Frage in Wirklichkeit aber gar nicht so leicht ist, macht man den Umweg und erklärt, was eine Maschine überhaupt tun kann. Dieser Umweg über die Frage, was Maschinen überhaupt tun können, macht einen auf eine Schwierigkeit aufmerksam. Denn im Spektrum zwischen ganz einfachen Maschinen (zum Beispiel eine Kaffee- oder Pfeffermühle) über kompliziertere (zum Beispiel ein Auto oder ein Rasenmäher) bis hin zum großen Bruder der künstlichen Intelligenz, der natürlichen Intelligenz, ist es ein sehr weiter Weg. Und wer ihn geht, weiß nicht, wie und wann er am Ziel ankommen wird. Denn in vielen Fällen läßt es sich gar nicht oder nur sehr schwer angeben, worin die höhere Komple- xität von Stufe zu Stufe eigentlich besteht. Ein Ausweg aus dieser Misere ist aber die Tatsache, daß man immer an- geben kann, wofür man eine bestimmte Maschine gebrauchen kann - sei es nun eine Kaffemühle, ein Auto oder unsere natürliche Intelligenz. Und in gleicher Weise ergeht es uns mit dem Computer. Auch bei ihm kann wenigstens gesagt werden, wofür wir ihn einsetzen können und welchen Nutzen er uns bringen kann, wenn wir auch nicht immer klar sehen, wie wir ihn diesem Nutzen zuführen sollen: wie wir also ein bestimmt es Programm schreiben müssen, daß der Computer so funktioniert, wie man es sich vorgestellt hat. In diesem Sinne läßt sich die Maschine "Computer" in vier unterschied- liche Sprachstufen einteilen. Auf jeder Stufe kann dieser bestimmte Aufgaben erfüllen, bestimmte andere Aufgaben dagegen nicht. Auf der untersten Stufe sind es nur sehr elementare Aufgaben, auf der nächst höheren besitzt der Computer bereits eine gewisse Merkfähigkeit, d.h. er hat einen elementaren Speicher, wodurch die durch ihn zu erledigen- den Aufgaben schon komplizierter sein können. Auf der höchsten Stufe ist der Computer dann universell einsetzbar, d.h. sein Speicher ist so groß, daß er jede ausreichend beschriebene Aufgabe erfüllen kann. Ein Computer mit einem universellen Sprachum- fang ist das Modell des heutigen Rechenautomaten, einer universellen Maschine also, die wiederum die Basis für die sogenannte Künstliche Intelligenz abgeben soll. Um verstehen zu können, was den Hintergrund Künstlicher Intelli- genz ausmacht oder ausmachen soll, wird es hier um die Sprachstufen gehen, die zu solchen Maschinen führen, auf denen Künstliche Intelli- genz möglich sein soll. Allen Sprachstufen, von denen es insgesamt vier gibt, ist ein in Tur- bo-Pascal geschriebener Interpreter gewidmet. Dieser soll jedem Inte- ressierten erlauben, jeweils eigene Programme zu diesen Automaten und Sprachstufen zu entwickeln und ablaufen zu lassen. Automatentheorie, Regeln und Zeichenketten Die Beschäftigung mit Sprachen und Sprachumfängen sind Thema der Auto- matentheorie. Dort werden dann Computer einfach nur Automaten genannt. Man kann das Ganze dann auch so nennen: Die Automatentheorie beschäf- tigt sich mit den Möglichkeiten und Grenzen der automatischen Reali- sierbarkeit von natürlicher Intelligenz, wobei hier Intelligenz alles umfaßt, was Nachdenken erfordert: also das Erringen des Nobelpreises für Mathematik ebenso wie das Errechnen des maximal verfügbaren Bud- gets für den nächsten Schallplattenkauf. Hintergrund dieser automati- schen Realisierbarkeit von natürlicher Intelligenz sind die formalen Sprachen. Formale Sprachen sind Mengen aus Regeln und Grundzeichen. Die Regeln besagen dabei, wie aus diesen verfügbaren Grundzeichen Zei- chenket ten gebildet werden können, oder sie können entscheiden, wel- che Zeichenketten zu einer bestimmten Sprache gehören und welche nicht. Oder nochmals anders gesagt: Die Regeln, die eine bestimmte Sprache ausmachen, können zur Analyse und zur Synthese von Zeichenket- ten verwendet werden. Bei der Analyse wird eine bestimmte Zeichenkette auf ihre Bestandteile reduziert. Sind die Bestandteile Elemente der Grundzeichen, dann gehört die Zeichenkette zu der Sprache, die durch die Regeln beschreibbar ist; sind sie nicht Elemente der Grundzei- chen, dann gehört die Zeichenkette nicht zu dieser Sprache. Bei der Synthese wird umgekehrt vorgegangen: Die Regeln bilden aus den Grund- zeichen Zeichenketten, und alle Zeichenketten, die aus den Grundzei- chen durch Anwendung der Regeln gebildet werden können, gehören zu dieser Sprache. Folglich, da die Kombinationsmöglichkeiten zwischen Grundzeichen und Regeln endlos zu sein scheinen, kann eine anscheinend nicht-abbrechende Menge von Wörtern einer bestimmten Sprache erzeugt werden. Je nach Komplexitätsstufe der Sprache, das heißt ihrer Regeln, ist also die Anzahl der erzeugbaren Wörter kleiner oder größer - bis hin zu universellen Sprachen, von denen man glaubt, daß in ihnen sogar natürliche Intelligenz höherer Stufe darstellbar sei. Man kann eine solche Realisation von Sprachen auch Algorithmus nennen. Denn auch Algorithmen sind solche formalen Grammatiken, durch die Ein- gabedaten eindeutig Ausgabedaten zugeordnet werden. Entsprechen die Eingabedaten über Regeln (die Be fehle des Programms) den Grundzeichen, also den Zeichen, die vom zuge- hörigen Algorithmus verarbeitet werden können, dann kann die Folge der Eingabedaten als ein Wort der Sprache betrachtet werden, die durch den Algorithmus realisiert wird. Folglich stellen auch alle Algorithmen, die auf Computern abgelaufen sind oder jemals ablaufen werden, Sprachen dar, die durch eine bestimmte Zahl von Regeln und Grundzei- chen definiert sind. Korrespondenz zwischen Sprachstufen und Automat Kommen wir nun aus dem Reich der künstlichen Intelligenzen zurück in die Realität maschineller Hausmannskost. Die spartanische Realität der Informatik besteht darin, daß wir es bei unseren Computern mit soge- nannten universellen Automaten zu tun haben. Dies besagt in einer Art intuitiver, also keineswegs bis ins Letzte gewissen, Überzeugung, daß jede Rechenvorschrift oder jedes Programm, das auf irgendeinem be- stimmten universellen Automaten ausführbar ist, auch auf jedem ander en universellen Automaten ausführbar sein muß. Da wir nicht alle Pro- gramme auf allen Computern ausprobieren können, um dieser Überzeugung ganz sicher sein zu können - so wie man auch nicht ausprobieren kann, ob alle Kochrezepte in allen Küchen realisierbar sind -, spricht man von einer nur intuitiven Gewißheit: das heißt einfach nur, daß bislang keine Ausnahme von dieser ungeschriebenen Regel bekannt geworden ist. Jedoch gibt es unterhalb der Grenze dieser universellen Automaten sol- che Automaten, auf denen nur ganz bestimmte Programme ausführbar sind. Hier seien sie einfach der Reihe nach aufgezählt: Der berühmteste uni- verselle Automat ist die sogenannte Turing-Maschine. Unterhalb dieser Maschine gibt es folgende Automaten: der linear beschränkte Automat, der Keller-Automat und unter diesen der endliche Automat mit und der endliche Auto mat ohne Ausgabe. Diese Automaten und ihr Bezug zu den entsprechenden Spachen der Automatentheorie können anhand der soge- nannten Chomsky-Hierarchie dargestellt werden: Chomsky-Typ Sprachen-Typ Automaten-Typ ----------------------------------------------------------- Typ-0 allgemeine Sprache Turing-Maschine (rekursiv-aufzählbar) Typ-1 Kontextsensitive linear beschränkte Sprachen Automat Typ-2 Kontextfreie Sprachen Kellerautomat Typ-3 Reguläre Sprachen endlicher Automat mit/ohne Ausgabe Wir werden nun jede dieser Sprachen und Maschinen von der einfachsten bis zur universellen Stufe betrachten. Dabei wird insbesondere auf die Struktur der auf diesen ablauffähigen Programme bzw. Sprachen und de- ren Grammatiken eingegangen. Sprach- und Grammatikformen der Automaten I) DIE SPRACHEN In der Welt aller Kochrezepte und aller Küchen lassen sich unter- schiedliche Schwierigkeitsgrade unterscheiden. In der Welt der Spra- chen und Grammatiken ist das ähnlich: Es lassen sich insgesamt vier Sprachstufen unterscheiden. Mit wachsender Komplexität und Umfang sind das die regulären Sprachen, die kontextfreien Sprachen, die kontext- sensitiven Sprachen.und die unbeschränkt-allgemeinen Sprachen (d.h. die rekursiv-aufzählbaren). In der Automatentheorie wird gezeigt, daß in diesen Grammatiken von Stufe zu Stufe unterschiedliche Regelformen zur Anwendung kommen. Jeder dieser Stufen oder Sprachen und Regelfor- men entspricht dann genau ein Automat. Das sind dann mit wachsender Komplexität die schon genannten Automaten: der endliche Automat mit/ohne Ausgabe, der Kellerautomat, der linear beschränkte Automat und die Turing-Maschine. Zum besseren Verständnis beginnen wir einfach mit dem Begriff der Regel und stellen dann die verschiedenen Regelformen bezüglich der unterschiedlichen Sprachstufen vor. Eine Regel ist ganz allgemein eine bestimmte, für einen konkreten Fall festgelegte Handlungsanweisung. Sie verbindet zwei Aussagen miteinan- der unter dem Primat der Wenn-dann-Beziehung: "Wenn .x, dann y". Eine Regel ist damit eine Handlungsvorschrift, wie sie in Kochrezepten oder Computerprogrammen vorkommt. Es sind Handlungsanleitungen, die mehr oder weniger mechanisch ausgeführt werden sollen, also eine Sache ge- nau für Computer und manche Köche. Eine Regel sagt: Wenn das und das der Fall ist, dann tue dieses. Man könnte sie also auch mit einer if- oder case-Anweisung irgendeiner Programmiersprache identifizieren. Auf einer sehr primitiven Basis sind Regeln Anweisungen der Form: A -> B. Diese Regel sagt aus: "Wenn A, dann B" bzw. "Aus A folgt B" bzw. "Wer A hat, der hat auch B" bzw. "Aus A kann man B ableiten" usw. Es ist also einfach wichtig zu wissen, was gemeint ist, wenn man von Regeln spricht; und daß es sich dabei auch um Handlungsanweisungen handeln kann, wie sie in Computerprogrammen oder Kochbüchern vorkom- men. Reguläre Sprachen Die regulären Sprachen sind für Maschinen mechanische Hausmannskost. Es ist die elementarste Stufe der Sprachen überhaupt, die von Compu- tern verarbeitet werden. Sie verfügen nur über rechts- und linksrekur- sive Regeln (genauer: rechts- und linkslineare Regeln). Rechts- und linksrekursive bzw. -lineare Regeln besitzen folgende Form: rechtsrekursive Regel: A -> aA linksrekursive Regel: B -> Bb Bei diesen Regeln kommt es nicht auf die Groß- und Kleinbuchstaben selbst an und nicht darauf wie sie heißen, sondern wichtig ist nur, daß auf der linken Regelseite nur Großbuchstaben und daß auf der rech- ten Seite der ersten Regel ein Klein buchstabe links vom Großbuchsta- ben (rechtslinear) bzw. auf der rechten Seite der zweiten ein Klein- buchstabe rechts vom Großbuchstaben (linkslinear) stehen muß. Bei den Großbuchstaben handelt es sich um sogenannte nicht-terminale Symbole (bzw. Variable), also um die Elemente VN = {A,B}; bei den Kleinbuchstaben um sogenannte nicht-terminale Symbole (bzw. Konstan- te), also um die Elemente VT = {a,b}. Nicht-terminale und terminale Symbole unterscheiden sich darin, daß die ersteren so lange durcheinander ersetzt werden müssen, bis die entstehende Zeichenfolge nur noch aus terminalen Symbolen besteht. Mithilfe der obigen beiden Regelformen sieht das folgendermaßen aus: Man verfügt über eine Anzahl von Regeln, zum Beispiel der folgenden Art: A -> a B -> b A -> Aa B -> Ab S -> Ba Mithilfe dieses Regelapparates P lassen sich folgende Zeichenketten erzeugen oder analysieren: S => Ba => Aba => Aaba => Aaaba => aaaba aaaaba => Aaaaba => Aaaba => Aaba => Aba => Ba => S Im ersten Fall wurde ausgehend vom Start-Symbol S durch schrittweise Regel-Anwendung eine Zeichenfolge erzeugt; im zweiten Fall wurde eine beliebige Zeichenfolge durch Anwendung des Regelapparates bis auf das Start-Symbol S reduziert. Im er sten Fall handelt es sich daher um eine Synthese (Generierung), im zweiten um eine Analyse von Zeichen- folgen. Kann im Laufe einer Analyse einer Zeichenfolge durch keine der möglichen Regel-Anwendungen das Start-Symbol S erreicht werden, so können genau zwei Fälle vorliegen: Erstens kann es sein, daß der vorliegende konkrete Regelapparat P nicht in der Lage ist, diese Zeichenfolge zu analysieren; dann muß ein anderer Regelapparat P' aus rechts- und linksrekursiven Regeln gefun- den werden, der diese Aufgabe erledigt. Zweitens besteht aber auch die Möglichkeit, daß eine Zeichenfolge vor- liegt, die durch keinen möglichen Regelapparat von links- und rechts- rekursiven Regeln analysiert werden kann. In diesem Fall ist der Be- reich von Wörtern und Sprachen, der durch links- und rechtsrekursive Regeln erfaßt werden kann, überschritten. Damit haben die regulären Sprachen, die auf der Basis von links- und rechtsrekursiven Regeln darstellbar sind, nur einen begrenzten und endlichen Umfang. Eine dieser regulären Sprachen kann jeweils durch einen solchen Regelapparat P beschrieben werden. Für die Veranschauli- chung dieser regulären Sprachen reichen die sogenannten endlichen Au- tomaten A mit bzw. ohne Ausgabe vollkommen aus. Man kann dafür auch sagen: L(G) = L(A), das heißt: Die Sprache L über G ist gleich der Sprache L über A. Oder: Die durch eine Grammatik der Form G = [VT, VN, P, S] symbolisierte Sprache ist gleich der Sprache, die aufgrund derselben Regeln durch einen Automaten A mit bzw. ohne Ausgabe überprüft bzw. erzeugt werden kann. Eine solche Grammatik ist folglich ein Quatrupel der Form G = [VT, VN, P, S] und besteht aus der Menge der terminalen Symbole VT, der Menge der nicht-terminalen Symbole VN, dem Regelappa- rat P und dem Start-Symbol S. Grenzen der regulären Sprachen und Sprachumfang der endlichen Automa- ten mit bzw. ohne Ausgabe So wie bestimmte Kochrezepte in bestimmten, schlecht ausgestatteten Küchen in keiner Weise Anleitung zur Herstellung einer leckeren Mahl- zeit sein können, gibt es auch bestimmte formale Sprachen, die auf der Basis von links- und rechtsrekursiven Regeln nicht dargestellt werden können. Es sind Sprachen höherer Komplexität. Die Grenzen der regulä- ren Sprachen sind aber zugleich die Grenzen des endlichen Automaten mit bzw. ohne Ausgabe. Denn, man erinnere sich, es gilt ja: L(G) = L(A). Deshalb soll hier nun eine solche Sprache angegeben werden, die über die regulären Sprachen und den Sprachumfang dieser endlichen Automaten hinausgeht. Eine solche Sprache ist zum Beispiel die Sprache mit der Form: L(G) = {x|x=anbn, n E N} über dem Alphabet E = {a, b}. Worte dieser Sprache sind Zeichenfolgen, die stets über dieselbe Anzahl von a- und b-Elementen verfügen: ab, aabb, aaabbb, usw. Um die Worte dieser Sprache L(G) = {x|x=anbn, n E N} erzeugen bzw. analysieren zu können, müßte dieser Automat in der Lage sein, sich die Anzahl der a-Elemente zu merken, um sie anschlie- ßend auf die b-Elemente zu übertragen. Diese Aufgabe leitet zu den kontextfreien Sprachen und dem zugehörigen Kellerautomat über. Kontextfreie Sprachen Die kontextfreien Sprachen verfügen nicht nur über links- und rechts- rekursive Regeln (genauer: links- und rechtslineare Regeln), sondern zusätzlich über die zentralrekursive Regel. Damit können in kontext- freien Grammatiken insgesamt drei Re gelformen auftreten: linksrekursive Regel: A -> A a rechtsrekursive Regel: A -> a A zentralrekursive Regel: A -> a A b Auch hier kommt es nicht auf die Bezeichnung von Klein- und Großbuch- staben an, sondern darauf, daß links nur ein Großbuchstabe und niemals Kleinbuchstaben stehen dürfen und rechts die Verteilung von Kleinbuch- staben wie eben angegeben erfolgen kann; genau genommen darf aber rechts der Regeln eine beliebige Folge von terminalen und nicht-termi- nalen Symbolen stehen. Mit Hilfe dieser drei Regelformen läßt sich für die Sprache L(G) = {x|x=anbn, n E N} eine Regelbeschreibung und damit eine Grammatik finden. Der zu dieser Sprache gehörige Regelapparat P besitzt nur zwei Regeln, die folgendermaßen lauten: A -> ab A -> aAb Die Wörter dieser Sprache werden also zentral von der Mitte her gebil- det oder so analysiert, daß zunächst von der Mitte ausgehend stets ein a- und ein b-Element entfernt wird. Durch die Entfernung immer nur eines a- und eines b-Elements wird sichergestellt, daß nur solche Zeichenfolgen als Wörter dieser Sprache analysiert werden können, die aus gleich vielen a- und b-Elementen bestehen: aaaabbbb -> aaabbb -> aabb -> ab -> A A -> ab -> aabb -> aaabbb -> aaaabbbb -> ... Ein Kellerautomat analysiert eine solche Zeichenfolge, indem er für jedes gelesene a-Element einen Eintrag in einem speziellen Speicherbe- reich macht. Wenn er schließlich zum Lesen der b-Elemente kommt, löscht er für jedes gelesene b-Element eines der gespeicherten a-Ele- mente, bis weder ein weiteres b-Element gelesen noch ein weiteres a- Element noch gelöscht werden muß. In jedem anderen Fall wäre entweder dieser spezielle Speicherbereich nach dem Lesen aller b-Elemente noch nicht leer oder der Speicherbereich wäre bereits leer, ohne daß alle b-Elemente bereits gelesen wurden. In diesen letzten beiden Fällen würde der Kellerautomat die Verarbeitung der Zeichenfolge vorzeitig abbrechen. Mit diesem Abbruch würde er dann anzeigen, daß das Eingabe- wort nicht zu dieser Grammatik gehört. Hintergrund der oben eingeführten Sprache L(G) = {x|x=anbn, n E N} ist eine kontextfreie Grammatik, die durch Kellerautomaten dargestellt werden kann. Der Grund dieser Fähigkeit des Kellerautomaten liegt dar- in begründet, daß dieser eine gewisse Merkfähigkeit besitzt, der an einen Stack erinnert: Das heißt, er kann sich durch Lesen und soge- nanntes Abkellern der a-Elemente ihre Zahl merken, um sie anschließend feldweise mit den b-Elementen zu vergleichen. Folglich darf man davon ausgehen, daß die kontextfreien Grammatiken einschließlich der Gram- matiken der regulären Sprachen zum Sprachumfang des Kellerautomaten gehören. Es sollte damit gezeigt werden, daß für diesen Fall folgende Beziehung Gültigkeit hat: L(G) = L (KA). Es besteht also Übersetzbarkeit zwischen kontextfreien Sprachen und dem Kellerautomat. Grenzen der kontextfreien Sprachen und Sprachumfang des Kellerautomaten Zwar besitzt der Kellerautomat einen größeren Sprachumfang als der endliche Automat mit und ohne Ausgabe; jedoch kann auch für den Kel- lerautomaten eine Sprache angegeben werden, für die dieser Automat keinen Akzeptor darstellt. Eine solche Sprache hat zum Beispiel mit dem Alphabet E = {a, b, c} folgende Form: L(G) = {x|x=anbncn, n E N}. Die Worte dieser Sprache sind beispielsweise abc, aabbcc, aaabbbccc, usw. Diese Worte besitzen stets die gleiche Zahl an a-, b- und c-Elementen. Beim Kellerautomaten rührt die Nicht-Akzeptanz dieser Sprache vom Bau seines Speichers her; denn er wird beim Lesen der a-Elemente deren Anzahl in seinem Speicher vermerken, um sie dann auf die folgenden b- Elemente zu übertragen. Dies hat a ber zur Folge, daß er danach keine Möglichkeit mehr besitzt, die verbleibenden c-Elemente zu überprüfen, denn nach Überprüfung der b-Elemente ist durch Löschen der a-Elemente dieser Speicher wieder leer. Diese Schwierigkeit betrifft in gleicher Weise die kontextfreien Spra- chen. Denn durch die bei diesen zur Anwendung kommenden Regelformen können lediglich die gleiche Anzahl der a- und b-Elemente durch gleichzeitiges Streichen je eines Elem entes von jeder Art überprüft werden. Auch hier bleibt anschließend keine Möglichkeit mehr, die An- zahl der c-Elemente zu testen. Daraus ergibt sich die Folgerung, daß eine Sprache der allgemeinen Form L(G) = {x|x=anbncn, n E N} über dem Alphabet E= {a, b, c} weder durch das Regelsystem kontextfreier Grammatiken noch durch die Vorge- hensweise eines Kellerautomaten dar gestellt werden kann. Kontextsensitive Sprachen Die Sprache mit der allgemeinen Wortform "anbncn" gehört zu den kon- textsensitiven Sprachen. Diese Sprachen zeichnen sich dadurch aus, daß auf der rechten und linken Regelseite beliebig viele terminale und/oder nicht-terminale Symbole stehen dürfen. Damit können kontext- sensitive Grammatiken Regeln enthalten, die nur umgebungsabhängig an- gewendet werden können. Damit liegen für die kontextsensitiven Spra- chen und ihre Regeln keine Einschränkungen mehr vor - allerdings mit Ausnahme der einen, daß bei der Analyse von Zeichenfolgen das Wort stets kürzer und bei der Synthese bzw. Generierung das Wort stets län- ger werden muß. Und um nochmals das Beispiel des Kochs zu traktieren: Auch er darf nur weitere Zutaten in die Brühe hineinwerfen und kann keine mehr heraus- holen, und dennoch muß das Ganze zu einer geschmackvollen Suppe werden - ansonsten könnte seine Karriere ein jähes Ende nehmen. Die allgemeinen Regelformen in kontextsensitiven Grammatiken haben daher folgendes Aussehen: linksrekursive Regeln: A -> Aa rechtsrekursive Regeln: B -> bB zentralrekursive Regeln: A -> aAb kontextsensitive Regeln: aA -> Aa Aa -> Aa aAb -> Aa Ein Regelapparat, der die oben angeführte Sprache mit der allgemeinen Wortform "anbncn" analysieren bzw. generieren kann, hat auf der Basis der terminalen und nicht-terminalen Symbole VT und VN die Form P: VT = {a, b, c,} VN = {A, B, S} P: S -> aB S -> aSA B -> bc cA -> Ac BA -> bBc Mit Hilfe dieses Regelapparats kann die oben angegebene Sprache analy- siert oder deren Worte generiert werden. Dazu ein Beispiel: S => aSA => aaSAA -> aaaBAA => aaabBcA => aaabBAc => => aaabbbBcc => aaabbbccc aaabbbccc => aaabbBcc => aaabBAc => aaabBcA => aaaBAA => => aaSAA => aSA => S Es läßt sich nun zeigen, daß für jede kontextsensitive Grammatik eine "Turing-Maschine" im Sinne eines linear beschränkten Automaten exi- stiert, so daß gilt: L(G) = L(LA); denn der linear beschränkte Automat geht so vor, daß er zunächst durch elementeweises Löschen von links nach rechts die Anzahl der a- und b- Elemente miteinander vergleicht. Folgt auf das zuletzt gelöschte b- Element ein c-Element und ist dann ebenso kein a-Element mehr vorhan- den, dann stimmt die Zahl der a- und b-Elemente überein. Dasselbe Ver- fahren wird nach Wiederauffüllen der a- und b-Elemente dann auf die b- und c-Elemente angewandt. Folgt schließlich auf das letzte c-Element ein Leerzeichen und ist dann auch kein b-Element mehr vorhanden, dann ist gezeigt, daß die Anzahlen aller drei Elemente übereinstimmen. Das analysierte Wort gehört damit zu dieser Sprache L(G). Differenzierung in linear beschränkten Automaten und Turing-Maschine Der linear beschränkte Automat unterscheidet sich von einer Turing- Maschine darin, daß er ein zweiseitig beschränktes Band besitzt. Die Turing-Maschine besitzt hingegen nur ein einseitig beschränktes Band. Dadurch besitzt sie den allgemeinsten Sprachumfang. Nach intuitivem Verständnis dürfte es daher keine Grammatik zu einer Wortform geben, die nicht durch eine Turing-Maschine darstellbar ist. Denn auf glei- chem Wege wie oben beschrieben könnte von einer Turing-Maschine auch die Sprache mit der Wortform anbncndn über dem Alphabet E = {a, b, c, d} berechenbar sein usw. Desgleichen könnte eine kontextsensitive Grammatik gefunden werden, die diese Aufgabe erfüllt. Folglich kann man auf dieser vierten Stufe der Sprachen innehalten, zurückschauen und sich ruhig zurücklehnen. Denn für jeden möglichen Fall scheint eine Lösung bereitzustehen und auffindbar zu sein. Deshalb bleibt an dieser Stelle auch nur noch eines zu tun: einen Interpreter für alle diese gefundenen Maschinen und Sprachen zu entwickeln und vorzustel- len. Das soll nun geschehen, und zwar gesondert für jede Maschine. II) DIE AUTOMATEN Der endliche Automat ohne Ausgabe Ein endlicher Automat ohne Ausgabe wird durch drei Mengen definiert: durch das Eingabealphabet E, seine Zustände S und die Überführungs- funktion. Das Eingabealphabet umfaßt diejenigen Zeichen, die der Auto- mat liest und verarbeitet. Die Menge der Zustände S umfaßt diejenigen Zustände, die der Automat im Laufe seiner Verarbeitung einnimmt. Zu dieser Menge gehören auch der Anfangszustand und die Menge der Endzu- stände. Das Programm eines solchen Automaten besteht aus dreiteiligen Regeln mit folgender Form: si, ai, sj Der Parameter si bezeichnet die Regelnummer. Dabei bilden alle Regeln mit derselben Ordnungszahl i zusammen einen Maschinenzustand. Der Parameter ai stellt die Aktion dar. Er stimmt im aktuellen Zustand si mit dem Eingabealphabetszeichen a uf dem Leseband überein. Der Parame- ter sj steht für eine neue Regel, zu der von der aktuellen Regel aus verzweigt werden soll. Er steht also für eine Verzweigungsregel. Die Zeichenverarbeitung eines endlichen Automaten ohne Ausgabe erfolgt in folgender Weise: Bevor die neue Regel sj ermittelt werden kann, wird das Leseband um ein Feld nach links bewegt. Dann wird vom Lese- band das neue Zeichen ai gelesen und zusammen mit der Nummer sj der aktuellen Regel eine neue Regel gesucht. Wird eine solche Regel aus der Kombination von sj und ai gefunden, wird diese Regel die neue ak- tuelle Regel, während das Leseband erneut um ein Feld nach links be- wegt wird usw. Mit der Verzweigungsregel sj der nun aktuellen Regel beginnt dieser Verarbeitungszyklus von Neuem. Der endliche Automat muß also in seinem Regelapparat P von Verarbeitungsschritt zu Verarbei- tungsschritt eine Regel finden, die in den ersten beiden Parametern eine Kombination aus Verweisungsregel der bisher aktuellen Regel und dem neu eingelesenen Eingabealphabetszeichen darstellt. Ist diese Regel vorhanden, kann der Automat zu dieser neuen Regel übergehen und seinen Verarbeitungsprozeß fortsetzen; wenn nicht, bricht der Automat die Bearbeitung des Lesebandes vorzeitig ab. Bei Abbruch des Verarbeitungsprozesses hat sich dann gezeigt, daß die auf dem Leseband niedergeschriebene Zeichenfolge nicht zu der im Regelap- parat des Automaten beschriebenen Grammatik gehört. Diese sehr elementare Weise der Verarbeitung von Zeichen eines Einga- bealphabets kann für einen Automaten mithilfe des Cartesischen Pro- dukts zwischen eingelesenem Zeichen und angezieltem Maschinenzustand beschrieben werden. Das Cartesische P rodukt beschreibt in diesem Fall die Überführungsfunktion u und hat für den endlichen Automaten A ohne Ausgabe folgende Form: u: E x S -> S Damit läßt sich der endliche Automat A ohne Ausgabe durch folgendes Quintupel A beschreiben: A = (E, S, u, sa, S), Dabei ist E das Einga- bealphabet, S die Menge der Maschinenzustände, u die Überführungsfunk- tion, sa der oder die Anfangszustände und S die Menge der Endzustände. Als Realisierung eines endlichen Automaten ohne Ausgabe kann man sich folgende Anordnung vorstellen: Der Automat benötigt als Instanzen eine Eingabe- und eine Verarbeitungseinheit. Als Eingabeeinheit verwendet man ein Leseband. Es hat sehr große Ähnlichkeit mit dem Schreibband eines Morsegerätes. Für dieses Leseband gilt wie beim Mor- segerät die Bedingung, daß es sich nur von rechts nach links bewegen kann. Dieses Band besteht zudem aus linear angeordneten Feldern, auf denen jeweils ein Zeichen des Eingabealphabets eingezeichnet sein kann. Alle mit den Zeichen des Eingabealphabets beschrifteten Felder ergeben von links nach rechts gelesen das Eingabewort. Alle übrigen Felder des Bandes sind leer oder tragen die Beschriftung mit einem Leerzeichen. Über diesem Leseband ist ganz links ein Lesekopf (L-Kopf) angebracht. Dieser Lesekopf liest stets das Zeichen des unter ihm be- findlichen Feldes. Danach wird das Leseband um eine Stelle nach links gerückt, während mithilfe des gelesenen Zeichens und der Verweisungs- nummer im Regelapparat des Automaten der neue Zustand des Automaten ermittelt wird. Programm zum endlichen Automaten ohne Ausgabe Für einen endlichen Automaten ohne Ausgabe kann auf der obigen Regel- form basierend folgendes kleines Programm mit dem Namen DUAL.A angege- ben werden: 000,1,000 ; PROGRAMM: Test auf 1er-Gruppen, die max. durch eine 000,0,010 ; Null getrennt sind 010,1,000 ; "010" ist elementare if-Anweisung: wenn 1, dann "000" 010,s,030 ; wenn 0, dann "030" 030,s,030 ; "s" ist Stopp-Zeichen Der Text nach dem Semikolon stellt dabei einen Kommentar dar, der beim Einlesen in den Programmeditor nicht berücksichtigt wird. Die Aufgabe des Programms besteht darin, Gruppen von Eins-Elementen danach zu testen, ob sie nur durch ein Leer-Element (hier die Null) getrennt sind. Die Bandinschrift vor Verarbeitungsbeginn kann damit folgendes Aussehen aufweisen: 11111011111111110110111110s Das "s" symbolisiert den Stop-Zustand. Vor Arbeitsbeginn steht der Lesekopf über der ersten linken Eins. Mit sukzessiver Kopfbewegung nach rechts wird Regel um Regel des Programms abgearbeitet. Gelingt die Verarbeitung im Ganzen, so wird de r gesamte Prozeß im Zustand "s" abgeschlossen. Damit gehört dieses Wort zu der durch den Regelapparat symbolisierten Sprache. Der endliche Automat mit Ausgabe Zwischen den endlichen Automaten mit und ohne Ausgabe besteht kein wesentlicher Unterschied. Der wichtigste Unterschied besteht allein darin, daß der endliche Automat mit Ausgabe zusätzlich über eine Aus- gabeeinheit verfügt. Die Ausgabeeinheit verfügt über ein Ausgabeband, auf dem in Abhängig- keit von Automatenzustand und eingelesenem Zeichen ein Ausgabezeichen feldweise eingetragen wird. Das Ausgabeband ist folglich identisch mit dem Leseband, nur daß über dies em statt einem Lese- ein Schreibkopf (S-Kopf) fest angebracht ist. Auch dieses Ausgabeband kann nur von rechts nach links bewegt werden, so daß die Ausgabezeichen auf ihm von links nach rechts eingetragen werden. Aufgrund des zusätzlichen Bandes ist der endliche Automat mit Ausgabe durch folgende Mengen definiert: Diese sind neben dem Eingabealphabet E und der Menge der Zustände S (einschließlich der Anfangs- und Endzu- stände) das Ausgabealphabet Z. Zusätzlich gibt es bei diesem Automaten neben der Überführungsfunktion u die Ausgabefunktion g. Ebenso wie die Funktion u kann die Funktion g als Cartesisches Produkt dargestellt werden: Sie gibt an, aufgrund welcher spezifischen Cartesisch en Produktbildung der Automat eine Ausgabe erzeugt. Jedoch wird in der Literatur die Ausgabefunktion nicht näher festge- legt, da hierbei Unterschiede auftreten können. Je nach Festlegung spricht man von einem Mealy-, einem Moore- oder einem trivialen bzw. Medwedew-Automaten. Gemäß dieser Reih enfolge haben diese drei endli- chen Automaten mit Ausgabe folgende zu unterscheidenden Ausgabefunk- tionen: g: E x S -> Z g: S -> Z g: E -> Z Damit kann der endliche Automat mit Ausgabe durch die folgende Menge M beschrieben werden: M = (E, S, Z, u, g, sa). Dabei ist E das Eingabealphabet, S die Menge der Zustände, Z das Aus- gabealphabet und sa der Anfangszustand, während u die bereits bekannte Überführungsfunktion und g die Ausgabefunktion darstellt. Damit be- sitzt der endliche Automat mit Ausgabe eine vierteilige Regelform: si, ah, zk, sj Die Regelnummer ist si, die Verzweigungsnummer sj. Die Variable ah stellt das Einlesezeichen dar, zk das Ausgabezeichen, das von der Ma- schine im Zustand si und beim Einlesen von ak ausgegeben wird. Beim endlichen Automaten mit Ausgabe steht im Zentrum des Interesses die Frage, welches Wort nach einem erfolgreichen Programmlauf auf dem Schreibband ausgegeben wird. Dabei korrespondiert die Grammatik der Eingabesprache einer anderen Grammatik als Ausgabesprache: Es wird ein Wort der Worteingabe-Grammatik genqau einem anderen der Ausgabe-Gram- matik zugeordnet. Gehört hier das Eingabewort nicht zur Grammatik der Eingabesprache, so kann ihm auch keines der Ausgabe-Sprache zugeordnet werden. Das heißt beide Sprachen stehen in einem maschinellen Überset- zungsverhältnis zueinander, das man allerdings auf der Basis solcher Sprachen nur mit einer sehr elementaren Übersetzungsbeziehung verglei- chen kann. Programm zum endlichen Automaten mit Ausgabe Dieses sehr bescheidene Programm UMKEHR.M für den endlichen Automaten mit Ausgabe basiert auf der zu diesem Automaten eingeführten Regel- form: 000,1,0,000 ; PROGRAMM: Umkehrung der Ein-/Ausgabe 000,0,1,000 000,s,s,000 Es hat zur Aufgabe, Einer- und Null-Elementgruppen des Eingabebandes in Null- und Einer-Elementgruppen zu verkehren, so daß zwischen Einga- be- und Ausgabeband ein komplementäres Wortverhältnis bezüglich der Symbole Eins und Null besteht. Zu Arbeitsbeginn hat das Leseband zum Beispiel folgende Inschrift: 111110001111001110000s Nach der Verarbeitung dieser Bandinschrift durch das Programm UMKEHR.M steht auf dem Schreibband das komplementäre Wort: 000001110000110001111s Damit wird die Verarbeitung im Zustand s, dem Stop-Fall, beendet. Die viereckigen Zeichen dienen als Leerzeichen. Der Keller-Automat Die endlichen Automaten mit und ohne Ausgabe können nur relativ zu einem bestimmten Maschinenzustand einen Zeichenvergleich zwischen Ma- schinenzustand und eingelesenem Zeichen durchführen. Da sie über eine Merkfähigkeit nur bezüglich des unmittelbar vom Leseband gelesenen Zeichens verfügen, also keinen darüber hinausgehenden Speicher besit- zen, sind sie nicht in der Lage, ein Zeichen für einen späteren Verar- beitungsschritt "aufzubewahren". Endliche Automaten mit und ohne Aus- gabe sind insofern vergleichbar mit schlechten Köchen. Sie verfügen nicht über Vorräte für schlechte Zeiten. Beim Kellerautomaten ist das anders: Er besitzt einen sogenannten Kel- ler. Auch er hat wie der endliche Automat mit Ausgabe zwei Bänder: ein Leseband mit einem darüber angebrachten Lesekopf (L-Kopf), das feld- weise nur von links nach rechts bewegt werden kann, und ein zweites Band, der sogenannte Keller, der von ihm als Speicherband, d.h. als Lese- und Schreibband, verwendet werden kann. Über ihm ist ein Schreib-Lese-Kopf (SL-Kopf) angebracht. Das Kellerband hat ein unteres Ende, während es nach oben offen ist. Es kann in beiden Richtungen bewegt werden. Das Kellerband funktioniert genau wie ein Stack: Der Automat kann im- mer nur ganz oben auf dem Kellerband ein Zeichen einfügen, und er kann auch immer nur das oberste der "abgekellerten" Zeichen lesen und lö- schen, niemals aber ein darunterliegendes. Ein Kellerautomat kann damit durch die folgende Menge KA beschrieben werden: KA = (E, S, K, sa, ka, u, S) Dabei ist E das Eingabealphabet, S die Menge der Zustände, K das Kel- leralphabet, sa der Anfangszustand, ka das Kellerstartzeichen, S die Menge der Endzustände und u die Überführungsfunktion. Es ist dabei zu beachten, daß das leere Zeichen k ein Element von E ist und damit auch nicht in einem Eingabewort vor- kommen kann. Dagegen gehört das leere Zeichen zur Menge K. Der SL-Kopf kann es auf das Speicherband schreiben, um damit ein über das Leseband eingegebenes und abgespeichertes Zeichen wieder zu löschen. Genauer müßte man sagen: Es gibt kein leeres Zeichen, sondern nur eine Kellerbandbewegung ohne Zeichenverarbeitung bzw. das Löschen eines Zeichens des Kelleralphabets plus einer Bandbewegung. Die Überführungsfunktion des Kellerautomaten hat die Form: u: (E U |φ|) x S x K -> S x K* Sie hat folgende Bedeutung: Es wird ein geordnetes Tripel (ei, sj, ku), bestehend aus einem Zeichen des Eingabebandes, dem aktuellen Zu- stand des Automaten und einem auf dem Kellerband unter dem SL-Kopf eingetragenen Zeichen, in das geordnete Paar (sn,t) überführt; dabei ist sn der neue Zustand und t als Element von K* ein Wort, das durch eine Verkettung des letzten Eingabezeichens mit dem zuletzt abgekel- lerten Zeichen gebildet und durch das oberste Kellerzeichen ersetzt wird. Zu Beginn der Abarbeitung befindet sich der Kellerautomat im Zustand sa, der Lesekopf steht über dem linken Zeichen des Lesebandes und der SL-Kopf über dem untersten Zeichen ka des Kellers. Steht bei der Bear- beitung eines Eingabewortes W un ter dem Lesekopf das Zeichen ej, un- ter dem SL-Kopf das Zeichen ku und befindet sich der Kellerautomat gerade im Zustand sj, dann kann es zu folgenden Vorgängen kommen: 1) falls es in u kein Tripel (ei,sj,ku) oder (φ, sj, ku) gibt, bleibt der Kellerautomat stehen; 2) falls es in u eine Zuordnung (ei, sj, ku) -> (sn, kt) gibt, dann geht der Kellerautomat in den Zustand sn über, ku wird durch kt ersetzt und das Eingabeband um ein Feld nach links bewegt; dann steht der SL-Kopf über dem letzten Zeichen von kt; 3) falls die obige Zuordnung statt ei das leere Zeichen φ bzw. kein Zeichen enthält, erfolgen dieselben Vorgänge wie zuvor, außer daß das Eingabeband nicht bewegt wird; 4) falls auf der rechten Seite einer Zuordnung das Paar (sn,φ) steht, so geht der Kellerautomat in den Zustand sn über und schreibt das Zeichen φ auf das Kellerband; er löscht also das dort stehende Zeichen ku und bewegt danach das Kellerband um ein Feld nach oben; 5) falls sn ein Element aus Σ ist und das Speicherband leer ist, bleibt der Kellerautomat stehen. Ein Eingabewort W E E* [Soll heißen: "W ist ELEMENT von E*"] aus der Sprache L(KA) gehört demnach dann zu einem Kellerautomaten KA, wenn dieser beginnend auf dem linken Zeichen von W und auf dem untersten Feld des leeren Speicherbandes eine Reihe von Zuständen durchläuft und schließlich auf dem am weitesten rechts stehenden Zeichen des Wortes W stehen bleibt, dabei der Kellerspeicher leer ist und KA einen Endzu- stand aus der Menge Σ erreicht hat. Programm zum Keller-Automaten Dieses Programm mit dem Namen ÄQUI.K, was für "Äquivalenz" steht, hat die Aufgabe, zwei Einser-Gruppen auf gleiche Länge zu testen. Ist dies nicht der Fall, bricht die Keller-Maschine die Verarbeitung vorzeitig ab. Das Programm hat folgende Struktur: 000,1,k,1,010 ; PROGRAMM: Test, ob zwei Eins-Zahlengruppen gleiche 010,1,1,1,010 ; Länge besitzen 010,0,1,■,020 ; "■" steht für leeres Zeichen 020,0,1,■,020 020,s,k,k,020 Zur Strukturierung dieser Regeln sei nochmals verdeutlichend gesagt: Die erste Zahlenspalte ist der aktuelle Zustand der Maschine, die zweite das auf dem Leseband und die dritte Spalte das auf dem Keller- band momentan gelesene bzw. eingetrag ene Zeichen, während in der vierten Spalte das auf dem Kellerband einzutragende Zeichen und in der fünften Spalte die Verzweigungsregel enthalten ist. Die Turing-Maschine (der linear beschränkte Automat) Da der Unterscheid zwischen Turing-Maschine und linear beschränktem Automaten einfach darin besteht, daß der zweitere ein zweiseitig be- grenztes Band besitzt (siehe das "Turing"-Programm in der Zeitschrift "PASCAL International" 4/88, Seite 75ff), während alle anderen Funk- tionen dieselben sind, wird hier ausschließlich die Turing-Maschine besprochen werden. Die Turing-Maschine verfügt nur noch über ein Band, das zugleich als Schreib- und Leseband (SL-Band) verwendet wird. Während dieses Band der Turing-Maschine auf seiner linken Seite begrenzt ist, ist es auf seiner rechten als beliebig lang aufzufassen. Es kann von der Turing- Maschine beliebig weit nach rechts und wieder nach links bewegt wer- den. Über ihm ist ein Schreib-Lese-Kopf (SL-Kopf) angebracht, durch den der Automat Zeichen in jedes in endlicher Zeit erreichbare Feld setzen, löschen oder durch Gehen zum benachbarten Feld nach rechts oder links übergehen kann. Damit kann die Turing-Maschine immer einen bestimmten Bereich seines Bandes als Speicherabschnitt verwenden. Die Turing-Maschine ist damit nicht darauf angewiesen, immer nur das oberste abgekellerte Zeichen vom Speicher zu holen. Vielmehr k önnen beliebige Zeichen vom Band gelesen und gelöscht werden. Damit besitzt die Turing-Maschine gegen- über dem Kellerautomaten ein Speicherband, auf dem jederzeit an belie- biger Stelle notierte Zeichen zugänglich sind und beliebig Zeichen gelöscht und gesetzt werden können. Diese von Alan M.Turing im Jahre 1936 beschriebene Maschine diente ihm dazu, die Unentscheidbarkeit gewisser mathematischer Sätze der Arith- metik zu zeigen. Sie wurde als elementarer Vorgänger Großvater der heutigen Rechenmaschinen. Er hatte mit diesem Maschinenkonzept sozusa- gen als Nebenprodukt zu seinen eigentlichen Zielen eine Form eines universellen Rechenautomaten erfunden. Eine Turing-Maschine T ist durch folgende Menge bestimmt: T = (E, S,B, sa, Σ, u) Dabei bezeichnet E die Menge der Bandzeichen, S die Menge der internen Zustände der Maschine, B die Menge der Kopfbewegungen über dem Schreib-Lese-Band (SL-Band), sa den Anfangszustand, Σ die Menge der Endzustände und u die Überführungsfunktion. Die Überführungsfunktion hat dabei die folgende Form: u: (ei, sj) -> (ep, sq, br) Diese Funktion sagt aus, daß die Maschine aufgrund eines bestimmten Zustands und eines bestimmten gelesenen Bandzeichens in einen neuen Zustand übergeht, indem br E B [Soll heißen: "br ist Element von B"] durchgeführt wird, das heißt es wird eine neue Bandbeschriftung an der betreffenden Stelle erzeugt oder der Schreib-Lese-Kopf um eine Feld- stelle nach rechts oder links bewegt. In diesem neuen Feld liegt dann die Eingabe ep im Zustand sq vor. Wenn die Turing-Maschine denn Zu- stand sr E Σ [Soll heißen: "sr ist Element von Σ"] erreicht, bleibt sie stehen. Bei einer Turing-Maschine steht im Zentrum die Frage, ob der Verarbei- tungsprozeß nach endlicher Zeit abbricht und dabei ein Endzustand der zugehörigen Grammatik erreicht wurde. Ist der Verarbeitungsprozeß ab- gebrochen, ohne daß dieser Endzustand erreicht wurde, so liegt ein Eingabewort vor, das nicht Element der über der Grammatik erzeugbaren Wortmenge ist. Bricht jedoch der Verarbeitungsprozeß nicht ab - ja dann ist die Frage, ob er überhaupt jemals abbricht. Wenn nicht, dann wird es nicht feststellbar sein, ob er überhaupt jemals abbricht und das Eingabewort Wort der über der Grammatik bildbaren Wortmenge ist. Wenn ja, dann ist er abgebrochen und es ist je nach Abbruchsstelle genau dies feststellbar: ob das Eingabewort zu dieser Grammatik gehört oder nicht. Programme zur Turing-Maschine (linear-beschränkten Automaten) Hier seien nun verschiedene Programme vorgestellt. Das erste ist ein besonders für den linear-beschränkten Automaten geeignetes Programm, das zur Zeichensuche dient. Die Verarbeitung beginnt irgendwo zwischen zwei Einsen auf dem Schreib-Les e-Band, um sukzessive die Position der nächst liegenden ersten Eins zu finden. Das Band hat vor Arbeitsbeginn folgendes Aussehen: 000000000000000010000000000000000000000100000000 Das zugehörige Programm besitzt folgenden Regelapparat: 000,0,1,010 ; PROGRAMM: Suche der nächsten rechts oder links 010,1,l,020 ; stehenden Eins 020,0,l,030 030,0,1,040 040,1,r,050 050,0,r,050 050,1,0,060 060,0,r,070 070,1,s,200 ; Ende rechts 070,0,1,100 100,1,l,110 110,0,l,110 110,1,0,120 120,0,l,130 130,1,s,200 ; Ende links 130,0,1,040 Das nächste Programm dient der Addition zweier Einser-Zahlengruppen. Das zweite hat die Aufgabe, zwei Zahlengruppen voneinander abzuziehen. Es dient der Subtraktion. Das erste Programm mit dem Titel ADDIE- REN.TUR besitzt folgende Struktur: 000,0,r,000 ; PROGRAMM: Addition zweier Einsen-Zahlengruppen 000,1,r,010 010,1,r,010 010,0,r,020 020,1,r,020 020,0,l,040 040,1,0,040 ; Eins der zweiten Zahl in Null verwandelt 040,0,l,050 050,1,l,050 050,0,1,060 ; die Null zwischen den Zahlen in Eins verwandelt 060,1,l,070 070,1,l,070 070,0,s,070 Vor Arbeitsbeginn hat das Band zum Beipsiel folgende Struktur, wobei der SL-Kopf irgendwo auf den links stehenden Nullen steht: | 000000000001111111111011111000000000 Die Addition erfolgt nun so, daß die Null zwischen den Einsergruppen in eine Eins verwandelt wird, wobei zuvor noch die am weitesten rechts stehende Eins in Null verwandelt wurde. Das Ergebnis in diesem Falle wäre dann die Zahl 15 gewesen, wobei der SL-Kopf über der ersten Null nach der letzten rechten Eins stehen bleibt. Das zweite Programm mit dem Titel MINUS.TUR besitzt folgende Struktur: 000,*,l,001 ; PROGRAMM: Subtraktion zweier Einsen-Zahlengruppen 001,1,0,002 002,0,l,003 003,1,l,003 003,*,l,004 004,0,l,004 004,1,0,005 005,0,l,006 006,*,r,017 006,1,r,007 007,0,r,007 007,*,r,008 008,1,r,008 008,0,l,009 009,1,0,002 009,*,l,010 010,0,l,010 010,1,0,011 011,0,r,011 011,*,r,012 012,0,r,012 012,*,r,013 013,1,r,013 013,*,1,014 014,1,l,014 014,*,l,015 015,0,l,015 015,*,l,016 016,0,l,016 016,1,0,011 016,*,r,017 017,0,1,018 018,1,r,017 017,*,r,019 019,0,1,020 019,*,r,021 020,1,r,019 021,1,r,021 021,*,s,021 Hier fungiert als Leerzeichen der Stern "*". Also heißt vor Verarbei- tungsbeginn die Bandinschrift für die Subtraktion "5 - 3" in folgender Weise: | **************11111*111*************** Der SL-Kopf steht vor Arbeitsbeginn über dem ersten Stern nach der letzten Eins. Die TM-Maschine arbeitet nun so, daß sie nach dem gleichmäßigen Streichen der Einsen in den beiden Zahlengruppen die verbliebenen der linken Zahlengruppe im fr eien Sternfeld rechts außen einträgt. Danach werden die beiden Zahlengruppen wieder hergestellt, so daß sich folgende Bandinschrift als Ergebnis ergibt: | ****************11111*111*11**************** Ein weiteres Programm dient der Modulo3-Division mit dem Faktor drei. Das Programm besitzt den Titel MODULO3.TUR und besitzt folgenden Re- gelapparat: 000,*,l,000 ; PROGRAMM: Modulo-3-Division (mit Rest-Ausgabe) 000,0,l,000 000,1,0,001 ; 1. Zahl auf Null 000,*,r,020 ; Rest 001,0,r,001 001,*,r,002 002,*,1,003 003,1,l,003 003,*,l,004 004,0,l,004 004,1,0,005 ; 2. Zahl auf Null 004,*,r,020 ; Rest 005,0,r,005 005,*,r,005 005,1,r,006 006,1,r,006 006,*,1,007 007,1,l,007 007,*,l,008 008,*,l,008 008,0,l,009 009,0,l,009 009,1,0,010 ; 3. Zahl auf Null 009,*,r,020 ; Rest 010,0,r,010 010,*,r,011 011,1,r,011 011,*,1,012 012,1,r,013 013,*,l,014 014,1,*,015 015,*,l,014 014,*,l,000 ; erneuter Schleifenbeginn 020,0,1,021 020,*,r,022 021,1,r,020 022,1,r,022 022,*,s,023 Leerzeichen ist auch hier der Stern "*". Im Anfangszustand sieht die Bandinschrift zum Beispiel folgendermaßen aus: | *****************11111111**************** Diese TM-Maschine zur Modulo3-Division überträgt nun immer gestrichene Einsen in das freie rechte Feld. Bei der Anzahl drei werden diese wie- der gestrichen, um von Neuem zu beginnen. Zum Schluß steht diejenige Anzahl von Einsen im rechten Fe ld, die Rest dieser Modulo-Division sind. Dann wird die Einsen-Zahlengruppe wieder aufgefüllt. Die Bandin- schrift sieht dann folgendermaßen aus: | ***************11111111*11***************** In einem letzten Programm mit Namen ZAHLEN.TUR stellt die Turing-Ma- schine auf ihrem Schreib-Lese-Band die natürlichen Zahlen beginnend von der Eins ab dar. Dabei symbolisiert eine Eins die natürliche Zahl eins, zwei Einsen die natürliche Zahl zwei, drei Einsen die natürliche Zahl drei usw. Aufgrund der Programmierung des Interpreters mit Hilfe der Zeigerstruktur ist die Grenze dieser Zahlendarstellung die Größe des überhaupt verfügbaren Computerspeichers. Das Programm dieser TM hat folgenden Aufbau: 000,0,1,010 ; PROGRAMM: Generierung der natürlichen Zahlen 010,1,r,010 010,0,r,011 011,0,1,012 012,1,l,012 012,0,l,013 013,0,l,013 013,1,l,020 020,1,r,030 020,0,r,050 030,1,0,031 031,0,r,031 031,1,r,032 032,1,r,032 032,0,1,012 050,1,r,051 051,0,1,052 052,1,r,051 051,1,l,055 055,0,r,056 055,1,0,055 056,1,r,056 056,0,1,010 Die Bandinschrift zu Beginn trägt lediglich lauter Nullen. Startfeld für den SL-Kopf sollte wenigstens die 4. Position von links sein. Damit seien genügend Programme zur Turing-Maschine bzw. zum linear- beschränkten Automaten angegeben. Neben dem einfachen Ausprobieren sollten sie die Phantasie anregen, eigene Programme zu entwerfen. Denn hier ist durchaus Kreativität und G eschick gefragt. Im übrigen würde sich der Autor dieses Artikels freuen, wenn ihm ein Leser solche lauf- fähigen Programme zusenden würde. Also viel Spaß! III) Ergebnis Im Verlauf dieses Artikels wurde gezeigt, was Maschinen der Datenver- arbeitung überhaupt tun können. Man konnte sehen, daß man zwischen endlichen und unendlichen Maschinen, den sogenannten universellen Ma- schinen, unterscheiden muß. Es wurde weiterhin deutlich, was eine Grammatik und was eine auf der Basis eines Eingabealphabets und dieser Grammatik erzeugte Wortmenge ist. Damit stellen diese Grammatiken je- weils eine Sprache dar, die je nach Komplexität der zugehörigen Ma- schine automatisch erzeugt werden kann. Aus dieser Perspektive und im Blick auf eine Künstliche Intelligenz ergeben sich somit zwei grundsätzliche Fragen: Erstens stellt sich spätestens bei der Turing-Maschine, die ja Vorbild heutiger Rechenau- tomaten ist, die Frage, wann jemals ein bestimmter Verarbeitungsprozeß abbrechen wird. Da es aber keine auf irgendeinem Automaten darstellba- re Grammatik gibt, die es erlaubt zu testen, ob irgendein Algorithmus jemals abbrechen wird (denn sonst müßte diese Grammatik auf sich selbst angewendet werden können, was einen logischen Widerspruch dar- stellt!), wird diese Frage auch zu einer zentralen Frage einer Künst- lichen Intelligenz. Da aufgrund neuronaler Komplexität modellierende Systeme (heute noch) zu sehr langen Rechenzeiten führen, kann im Ein- zelfall nicht unbedingt sicher sein, wann und ob dieser bestimmte Pro- zeß jemals abbricht. Es müssen daher (im Rahmen der Automatentheorie natürlich) entspre- chende Hard- oder Software-Lösungen gefunden werden, die intelligente Leistungen auf ein vertretbares Maß an Rechenzeit verringern. Zweitens stellen Kritiker der Künstlichen Intelligenz die grundsätzli- che Frage, ob auf der Basis "mechanischer Rechenmaschinen" überhaupt intelligentes Verhalten dargestellt werden kann; denn die hohe Komple- xität des Gehirns und seiner Struktur scheint dies auszuschließen. Jedoch kann man darauf antworten, daß die Turing-Maschine universelle Möglichkeiten zur Verfügung stellt. Insofern darf man durchaus optimi- stisch sein. Nur: Die daran anschließende Frage darf man ernst nehmen, ob die Kapazität menschlichen Denkens überhaupt genügt, Mittel und Wege zu finden, menschliches Denken mechanisch zu reproduzieren - oder anders: Besitzt unser Gehirn selbst die Kapazität, sich zu reproduzie- ren. Oder: Wie hoch muß die Leistungsfähigkeit unseres Gehirns sein, um seine eigenen intelligenten Leistungen zu reproduzieren. Könnten dann, falls dies möglich sein sollte, Maschinen sich selbst produzie- ren - eine neue Form maschineller Fruchtbarkeit. Dieses Land Utopia ist heute und sicher in weiterer Zukunft eine Mi- schung aus Märchen und Frankenstein, einfach unrealistisch. Es ist eine platonische Idee, von der vielleicht auch manche Köche träumen mögen. Aber die Köche bleiben dann doch immer im kleinen: in ihrer Küche, wo es schließlich doch immer wieder nur darum geht, auf genüß- liche Art seinen heutigen Hunger zu stillen. Und so mag es der Künst- lichen-Intelligenz-Forschung auch immer wieder ergehen: Man backt nach dem Ausflug in die Phantasie und das Schlaraffenland doch immer wieder nur kleine Brötchen. (wr) Literatur: - Goldschlager/Lister: Informatik. Eine moderne Einführung. München 1. Auflage 1984: 3. Kapitel: Theorie der Algorithmen. (Inhalt: Eine allgemeine Einführung/Übersicht zum Thema Algorithmen) - Herschel, R.: Einführung in die Theorie der Automaten, Sprachen und Algorithmen. (München 1974) (Inhalt: ein sehr zu empfehlendes Buch, da es auf sehr einfache und sehr anschauliche Weise dem Anfänger die gesamte Automatentheorie nahe bringt und verständlich macht) - Hans Hermes: Aufzählbarkeit Entscheidbarkeit Berechenbarkeit. (Berlin 3. Auflage 1978) (Inhalt: zur Theorie der Turing-Maschine, ein bereits mathematisch sehr anspruchsvolles Buch) - Engeler/Läuchli: Berechnungstheorie für Informatiker. (Stuttgart 1. Auflage 1988) (Inhalt: ein weiterführendes Fachbuch zum Thema, nur für mathematisch Versierte zu empfehlen)