×

Automata studies. (English) Zbl 0074.11204

Annals of Mathematics Studies 34. Princeton, New Jersey: Princeton University Press. 296 p. (1956).
Contents:
Finite automata: S. C. Kleene, Representation of events in nerve nets and finite automata (3–41); J. von Neumann, Probabilistic logics and the synthesis of reliable organisms from unreliable components (43–98); James T. Culbertson, Some uneconomical robots (99–116); M. L. Minsky, Some universal elements for finite automata (117–128); Edward F. Moore, Gedanken-experiments on sequential machines (129–153).
Turing machines: Claude E. Shannon, A universal Turing machine with two internal states (157–166); M. D. Davis, A note on universal Turing machines (167–176); John McCarty, The inversion of functions defined by Turing machines (177–182); K. de Leeuw, E. F. Moore, C. E. Shannon and N. Shapiro, Computability by probabilistic machines (183–214).
Synthesis of automata: W. Ross Ashby, Designing automata (215–234); D. M. MacKay, The epistemological problem for automata (235–252); Albert M. Uttley, Conditional probability machines and conditioned reflexes (253–276); Albert M. Uttley, Temporal and spatial patterns in a conditional probability machine (277–286).
The collection on the whole and the articles will be reviewed individually (see below).
Book review: Die zwei Hauptthemen dieser Aufsätze –
1. das analytische Problem, die Intelligenz, die Funktion des Gehirns, usw., mit Hilfe eines mathematischen Modells zu erklären;
2. das synthetische Problem der Konstruktion von Automaten, die immer größere Aufgaben des menschlichen Denkens übernehmen –
gehören heutzutage eng zusammen. Die Verff. kommen von der Logik, Mathematik, Physik, Technik, Neurologie und Physiologie. Es ist den Herausgebern gelungen, mehrere auf so verschiedenen Gebieten bedeutende, z. T. mathematisch erstrangige Beiträge zu vereinigen, die eine gemeinsame, mit neurologischen und elektronischen Termen bereicherte mathematische Sprache sprechen, und sie so anzuordnen, daß der enge innere Zusammenhang deutlich erscheint. –
Endliche Automaten (M., = Maschinen; die beiden Worte sind durchgehend synonym) haben eine feste, endliche Anzahl möglicher (a) Zustände, (b) Ein- und (c) Ausgänge und sind durch zwei diskrete Funktionen definiert: Zustand und Ausgang in einem gewissen Moment (Zeitintervall) sind von dem in einer quantisierten, aber unbeschränkten Zeit unmittelbar vorhergehenden Zustand und Eingang eindeutig bestimmt. Dies entspricht wirklich gebauten M., wie auch unseren Vorstellungen vom Gehirn. Eine schon von Turing vorgesehene Variante läßt auch zufällige Prozesse eingreifen, d. h. ersetzt die eindeutigen Funktionen durch Wahrscheinlichkeitsfunktionen. Dies ist von größter praktischer und theoretischer Bedeutung, da ja auch deterministische Systeme infolge der Unvollkommenheit ihrer Bestandteile (Lampen, Nervenzellen, usw.) nicht absolut zuverlässig sein können und allgemein Information mit Geräusch verbunden ist. Eventuell kann auch der systematisch benutzte Zufall die Leistungsfähigkeit der M. erhöhen. Dagegen sind Turing-M. nicht endliche M., da die Länge des auf ihrem Band druckbaren Textes keine obere Schranke hat. Betrachtet man aber das Band als Teil der Umgebung, so ist die verbleibende ,,Turing-M. ohne Band” eine endliche M. mit dem jeweils nur ein einziges Symbol lesenden Eingangstor. Umgekehrt wird eine endliche M. unendlich, wenn man ihr unbeschränktes Gedächtnis, d. h. Aufbewahrungsmöglichkeit ihrer Ausgänge zu eventuell sinnvoller Wiederverwendung, gibt. Dementsprechend ist die Klasse der berechenbaren Zahlen im Sinne von Turing weiter als die der durch endliche M. berechenbaren. Letztere ist nach Kleene der Klasse der ,,regulären Ereignisse” (reg. E.) äquivalent. Ob das ,,wirkliche Denken” und das ,,sogenannte Denken” einer die menschliche Intelligenz nachahmenden oder sogar übertreffenden M. im Wesen verschieden oder identisch sind, mag wohl eine nicht hierhergehörige metaphysische Frage oder ein Scheinproblem sein. Das hebt jedoch nicht die komplizierte Struktur des in verschiedenen, mehr oder minder tiefen Schichten sich abspielenden Denkens auf. Eine wirklich intelligente und nützliche M. müßte zunächst imstande sein, den gegenwärtigen Stand einer wissenschaftlichen Disziplin wirklich zu ,,verstehen”, um sie weiterzuentwickeln. Äußerliche Nachahmung des Benehmens, d. h. Spezifizierung einer ,,Eingang-Ausgangsreaktion”, kann kein wichtiges synthetisches Problem lösen.
Review of articles: S. C. Kleene “Representation of events in nerve nets and finite automata” (3–41) geht von dem McCulloch-Pittsschen Modell eines Nervennetzes (NN.) aus [W. Pitts and W. S. McCulloch, Bull. Math. Biophys. 5, 115–133 (1943; Zbl 0063.03860)], und baut unabhängig die Theorie der ,,allgemeinen”, d. h. mit Zirkeln (= Rückkoppelung) versehenen NN. neu auf. Ein Ereignis (E.) ist eine Eigenschaft von möglichen Erfahrungen – Folge vergangener Eingänge bis zur Zeit \(p\) (Gegenwart) –, d. h. eine Teilklasse der Klasse aller a priori möglichen Tafeln (T.) (= ,,Geschichten”, ,,histories”) des (Eingangs-) Systems. Ein E. passiert, wenn die tatsächliche Vergangenheit zu dieser Teilklasse gehört. Die Klasse der regulären (reg.) T.-mengen enthält die leere Menge, die Einheitsmengen (d. h. eine einzige T. enthaltenden) und die aus diesen durch die folgenden drei binären Operationen herstellbaren T.-mengen: \(E \vee F\), Summe, Disjunktion oder Vereinigungsmenge von \(E\) und \(F\); \(EF\), ,,Produkt”, ist die Menge aller T., die zeitliche Aufeinanderfolge einer T. von \(E\) direkt nach einer T. von \(F\) sind; \(E * F\), ,,Iteration von \(E\) nach \(F\)”, ist \(F\vee EF\vee EEF\vee\cdots =\sum_{n=0}^\infty E^nF\). Ein E. ist reg., wenn es sich durch eine reg. T.-Menge darstellen läßt, d. h. dann und nur dann passiert, wenn die Vergangenheit zu einer reg. T.-menge gehört. Es wird bewiesen (Satz 3): Zu jedem reg. E. existiert ein NN., das es darstellt (durch Erregung eines inneren Neurons zur Zeit \(p+2\)); (Satz 5): Die durch einen Zustand einer endlichen M., also insbesondere auch eines NN. darstellbaren E. sind reg. Daraus folgt das Hauptergebnis: Die Klasse der durch NN. darstellbaren E. ist mit der der reg. E. identisch.
Es wird noch der Fall unendlicher Vergangenheit betrachtet, der Zusammenhang zwischen Regularität von E. und primitiver Rekursivität aufgezeigt, und ein mathematisch interessantes Beispiel eines irreg. E. gegeben.
Der Aufsatz von J. von Neumann “Probabilistic logics and the synthesis of reliable organisms from unreliable components” (43–98) ist eine Neubearbeitung von Vorträgen [Lectures on probabilistic logics and the synthesis of reliable organisms from unreliable components, California Inst. Techn. 1952), über die schon mehrmals berichtet wurde [H. H. Goldstine, Proc. Eastern Comput. Confer., Washington, Dec. 8–10, 1953, 96–98 (1954; Zbl 0057.10801)]. Es wird unter anderem die Rolle des Irrtums in der lebendigen Logik und in den sie darstellenden M. erforscht und die Möglichkeit der Irrtumskontrolle verständlich gemacht. Verf. hätte eine thermodynamische, den modernen Theorien der Information [L. Szillard, Z. Phys. 53, 840–856 (1929) ; C. E. Shannon, A mathematical theory of communication, Bell Syst.Techn. J. 27, 379–423 (1948)] ähnlichere Theorie seinen ,,ad hoc” gefundenen Resultaten vorgezogen. Der Ref. kann jedoch dieser Bescheidenheit des Verf. nicht zustimmen und hält es sehr wohl für möglich, ja geradezu für wahrscheinlich, daß die vom Verf. erfundenen und ,,Tricke” genannten Kunstgriffe wie ,,Mehrheitsorgan”, ,,vervielfältigte Leitungen”, ,,Wiederherstellungsorgan” und die aus Ziffern- und Analogteilen ,,gemischten Systeme” mehr als Tricke sind und eventuell einige der Ideen aufdecken, mit denen auch die Natur arbeitet. Für einen gewissen spezielleren Teil des Inhalts dieser Arbeit kann auf die oben erwähnte Besprechung (Goldstine, loc. cit.) verwiesen werden. Einige kommentierte Teilüberschriften mögen den Umfang dieser Arbeit illustrieren: 2. 1. Logics of automata – Eine M. ist ein in der Zeit verlaufendes, mit elementaren Verzögerungen (timelag, delays) versehenes Modell einer Logik. Das ist für die Ausschließung von Zirkelschlüssen usw. sogar von Vorteil. 3.2. Propositions, automata and delays. 4.1.2. The double line trick. 4.2.1. The Sheffer stroke. 4.2.2. The majority organ. 5. Logics and information. 5.1. Intuitionistic logics – Einführung der Rückkopplung für induktive Prozesse. 6.1. The memory unit. 6.2. Scalers. 6.3. Learning. 7. The role of error. 7.4. The multiple line trick. 9. The technique of multiplexing. 9.2.3. The restoring organ. 10.5. Complete quantitative theory – Statistische Analyse der Schefferstrichoperation in Bündeln. 11. Digitalization and multiplexing. 11.1. Various assumptions regarding the digital vs. analog character of the nervous system. 11.2. Random permutation (von Leitungen). 12.2. A possible analog procedure. 12.3. Algebraical calculus resulting from the above operations. 12.5. A plausible analog mechanism: Density modulation by fatigue. 12.6. Stabilization of the analog system. 13.1. A possible neurological interpretation.
James T. Culbertson beschreibt eine einfache, praktisch absurde Schaltungsmethode für beliebig vorgegebene Ein-Aus-Spezifikationen.
M. L. Minsky charakterisiert Grundelemente, die zum Aufbau beliebig vorgegebener Funktionen gewisser Klassen ausreiche.
Edward F. Moore fragt: Inwieweit kann die Struktur einer deterministischen M. durch Beobachtung ihres Benehmens (Reaktion auf Gedankenexperimente) erschlossen werden? Diese Fragen besitzen für gewisse Kategorien von M. und Experimenten mehr oder minder scharfe Antworten.
Claude E. Shannon betrachtet Turingsche Universal-M. mit \(m\) inneren Konfigurationen und \(n\) Symbolen. \(m\) oder \(n\) allein kann auf 2 heruntergedrückt werden; dagegen multipliziert sich das Produkt \(mn\) mit einem unwesentlichen Faktor (hier 6 oder 8). Der minimale Wert von \(mn\) (oder eine gute Abschätzung davon) sind unbekannt.
M. D. Davis schlägt eine neue, verhältnismäßig explizite und abstrakte Definition einer allgemeinen Turingschen Universal M. vor und motiviert diese Definition. Wesentlich ist ein Kriterium, das die Existenz einer rekursiven Funktion fordert.
John McCarthy stellt das Problem, eine Funktion \(g(m,r)\) aus der Funktionalgleichung \(f_m(g(m,r)) = r\) zu bestimmen, wo \(f_m(n)\) die zur \(m\)-ten Turing-M. gehörige Funktion ist \((m, n, r\) sind natürliche Zahlen). Es handelt sich um eine Interpretation des Begriffs ,,wohldefiniertes”, d. h. prüfbares intellektuelles Problem; dementsprechend ist das Problem bedeutend, aber schwierig. Die Existenz von \(g(m,r)\) ist allgemein unentscheidbar. Es wird angestrebt, die Lösung – soweit vorhanden – zu vereinfachen oder zu beschleunigen.
K. de Leeuw, E. F. Moore, C. E. Shannon und N. Shapiro untersuchen die Frage: Was kann eine mit zufälligen Elementen versehene M. mehr leisten als eine rein deterministische? Die Präzisierung dieser Frage erfordert einen im rein mathematischen Sinn hochtechnischen Apparat von Definitionen, Sätzen und langen Beweisen, die tiefere Mittel der reellen Funktionen- und Maßtheorie erfordern, und schränkt gleichzeitig den Geltungsbereich der Resultate scharf ein. Man benötigt zunächst eine neue, abstrakte Definition der M. als wohldefinierte Funktion, die beliebig langen, endlichen Folgen endliche Folgen so zuordnet, daß Anfangsstücke in Anfangsstücke abgebildet werden, woraus sich auch eine eindeutig bestimmte Fortsetzung der Funktion auf unendliche Folgen als Argumente ergibt. ,,\(p\)-M.”, \(0 < p < 1\), sind M., die mit unendlichen, zufälligen Folgen von \(1\)-en und \(0\)-en gefüttert werden, in denen \(1\) mit der Wahrscheinlichkeit \(p\) vorkommt. Die M. mag dann gewisse Folgen als Funktionswerte mit positiver Wahrscheinlichkeit produzieren, die entsprechend zwei verschiedenen Definitionen entweder stark oder schwach \(p\)-aufzählbar (\(p\)-berechenbar) heißen. Beide Begriffe werden sich unerwarteterweise als äquivalent herausstellen.
Ist das Argument eine bestimmte Folge \(A = \{a_1, a_2, \ldots\}\), so hat man den rein deterministischen Fall. Man benutzt insbesondere \(A_1 = \{1, 1, 1,\ldots\}\) und dementsprechend ,,1-aufzählbar”, ,,1-berechenbar” synonym mit ,,rekursiv-aufzählbar, -berechenbar”; und in ähnlicher Weise allgemein die Folge \(A_p = \) ,,binäre Entwicklung von \(p\)”.
Satz 1: ,,\(A_p\)-Aufzählbarkeit”, ,,schwache” und ,,starke” \(p\)-Aufzählbarkeit sind äquivalent.
Satz 3: Ist \(p\) eine berechenbare Zahl (d. h. 1-berechenbar), so ist jede (stark oder schwach) \(p\)-berechenbare Folge 1-berechenbar; ist dagegen \(p\) nicht berechenbar, so existieren stark und schwach \(p\)-berechenbare Folgen, die nicht 1 berechenbar sind. Daraus folgt z. B., daß eine ,,\(\tfrac 12\)-M.” nichtberechenbare Folgen höchstens mit verschwindender Wahrscheinlichkeit druckt. Es wird noch eine all gemeinere Klasse von sog. ,,stochastischen” M. definiert und erforscht. Alle diese Resultate sind nur von theoretischem Interesse, da sie offenbar für endliche Automaten keinen Sinn haben. [Ref. möchte noch folgende Frage stellen: Inwieweit, wenn überhaupt, kann eine ,,Zufallsvorrichtung” gedanklich realisiert werden, die Folgen mit nicht berechenbarem \(p\) erzeugt?]
Der dritte Teil ,,Synthesis of automata” ist, wie zu erwarten, der schwächere Teil des Buches, jedoch nicht uninteressant.
W. Ross Ashbys Aufsatz betont einseitig einen möglichen Aspekt der Ideen, die im Buche des Verf. “Design for a brain” (London, New York 1952) besser dargestellt wurden, ohne wesentlich neues hinzuzufügen. Die Beispiele und Argumente scheinen dem Ref. manchmal grob, oder sogar danebenzugehen. So ist im Sinne dieses Aufsatzes eigentlich jede Rechenmaschine ein ,,Intelligenzverstärker” und somit das Problem im Prinzip wie auch praktisch schon gelöst! Manchmal erscheint die von Verf. vorgeschlagene Lösung als eine gigantische, für diskrete Zeit modifizierte Analogmaschine (oder Servomechanismus), die sich rein empirisch einem Gleichgewicht nähert. Vor allem aber scheint er ein wichtiges, wenn auch oft unbeliebtes Organ vergessen zu haben, nämlich das, das (intelligent) fragen kann. Der mathematische Teil des Aufsatzes, formuliert in abstrakter Bourbaki-Terminologie, scheint dem Ref. ganz überflüssig; das bewiesene Theorem ist wohl trivial und seine Verständlichkeit noch durch einen fatalen Druckfehler gestört: In der letzten Formel der Bedingung (7) (S. 224) muß ein Gleichheitszeichen, und nicht \(+\), stehen.
D. M. MacKay kann fragen und macht von dieser Fähigkeit guten Gebrauch. Er untersucht die feinere Struktur des ,,Maschinendenkens” und kommt zu dem Ergebnis, daß ein mit Hilfe statistischer Prinzipien konstruierter Automat imstande ist, eigene Symbole für abstrakte Begriffe zu entwickeln, d. h. aber unabhängig vom menschlichen Konstrukteur begrifflich zu denken.
Albert M. Uttley zeigt, wie eine M. die Fähigkeiten von Tieren, bedingte Reflexe zu entwickeln und Ähnlichkeiten zu erkennen, nachahmen kann. Zu diesem Zweck wird die Klassifikationsfähigkeit auf die Enthaltenseinsrelation der Mengenlehre und der quasikausale Zusammenhang auf bedingte Wahrscheinlichkeit zurückgeführt. Beide Relationen können durch endliche Maschinen in gewissen Grenzen dargestellt werden. Klassifikation ist momentan (unter äußerst vereinfachenden Annahmen, die einer elementaren Wahrnehmung entsprechen wie z. B. Geschmack, Geruch). Im zweiten Aufsatz wird diese Theorie auch auf ,,Gestalten” (zeitliche und räumliche) ausgedehnt.
Reviewer: D. Tamari

MSC:

68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Qxx Theory of computing
00B15 Collections of articles of miscellaneous specific interest
Full Text: DOI