Zur Rezeption von McCulloch-Pitts

Aus Sicht der theoretischen Informatik bildet das Papier von McCulloch und Pitts (1943) [170] sicher einen historisch wichtigen Meilenstein in der Analyse des Gehirns aus Sicht der Berechenbarkeit. Die aus Sicht von McCulloch und Pitts wichtigsten Eigenschaften von Nervenzellen und Nervennetzen werden zusammengefasst und mit einer logischen Sprache (basierend auf Russel und Whitehead (1927)[230], Carnap (1938)[38] sowie Hilbert und Ackermann (1928)[111]) beschrieben. Diese Formalisierung erlaubte im Jahr 1943 ganz neuartige Einsichten in die Struktur und Dynamik neuronaler Netze. Interessant, wenn nicht gar verwirrend, ist die Rezeption dieses Artikels durch die Fachwelt.

Ein -das wichtigste?- Bindeglied zwischen dem Artikel von McCulloch und Pitts (1943) und der späteren Rezeption (z.B. durch Minsky (1967)[181]:Kap.3) ist die umfangreiche Arbeit von Kleene (1956)[136] (die wiederum auf eine frühere Arbeit von Kleene aus dem Jahr 1951 zurückgeht).

Kleene beschränkt sich bei seiner Rekonstruktion von McCulloch und Pitts (1943) auf jene Teile des Artikels, in denen Netze ohne Zyklen beschrieben werden. Diese Netze entsprechen deterministischen endlichen Automaten (DFA := deterministic finite automata), die die Menge der regulären Ausdrücke erkennen können. Dieser Automatentyp ist theoretisch deutlich schwächer als die Turingmaschine TM), aber in der Praxis -wie sich im Laufe der Jahrzehnte zeigte- von höchster Bedeutung.

Interessant ist allerdings, dass McCulloch und Pitts (1943) auch noch solche Netze betrachten, die Zirkel (circles) zulassen. Kleene begründet seine Auslassung dieser Abschnitte des Artikels damit, dass diese Abschnitte unverständlich (obscure) seien (vgl.Kleene (1956)[136]:P.4). In diesem Abschnitt kommen McCulloch und Pitts allerdings zu folgenden interessanten Feststellung (vgl. McCulloch und Pitts (1943) [170]:P.129):

1. McCP-These 1: Netzwerke mit Zyklen, die ein Band mittels geeigneten Vorrichtungen scannen und mittels geeigneter Motorik schreiben koennen, sind gleichmächtig mit einer Turingmaschine.
2. McCP-These 2: Netzwerke mit Zyklen, die ein Band mittels geeigneten Vorrichtungen scannen und mittels geeigneter Motorik schreiben koennen, können Netze mit Zyklen berechnen.
3. McCP-These 3: Netzwerke mit Zyklen, die kein Band haben, können eine echte Teilmenge der Zahlen berechnen, die auch eine Turingmaschine berechnen kann, und zwar genau die, die ein Organismus berechnen könnte.

Angenommen, diese Behauptungen liesen aus den Annahmen von McCulloch und Pitts in ihrem Artikel beweisen, wie verhielten diese sich dann zu den Ergebnissen der Automatentheorie nach Kleene?

Mittlerweile ist die Chomsky-Hierarchie allgemein akzeptiert, nach der es eine klare Stufung von Sprachklassen und zugehöerigen Automatentypen gibt (vgl. z.B. das Hierarchietheorem bei Hopcroft und Ullman (1979)[114]:P.228). Zahllose weitere Verfeinerungen existieren mittlerweile (eine sehr gute Übersicht gerade für Automaten bietet z.B. Schneider (2004)[232]). Aufgrund dieser Arbeiten wissen wir, dass zyklische Netze als Repräsentationen von endlichen (deterministischen und indeterministischen) Automaten aufgefasst werden können, die infinite Eingabewörter akzeptieren ( $\omega-Automaten$), d.h. die Zyklen als solche machen einen Automaten noch nicht zu einer Turingmaschine. Das, was die Stärke eines endlichen Automaten entscheidend erweitern würde, das wäre die Möglichkeit, minimale Formen von Gedächtnis (memory) nutzen oder ausbilden zu können. So unterscheiden sich z.B. die Kellerautomaten (Push Down Automata, PDAs), die kontextfreie Sprachen erkennen können und die Linear gebundenen Automaten (Linear Bounded Automata, LBAs), die kontextsensitive Sprachen erkennen können, von normalen endlichen Automaten alleine dadurch, dass sie zusätzlich einfache Speichermöglichkeiten besitzen, die sie immer näher an die Turingmaschine rücken, die unbeschränkt ein Band lesen und wiederbeschreiben kann.

Vor diesem Hintergrund bietet sich folgende erste Bewertung der Thesen McCP-These 1-3 an:

1. McCP-These 1: Interpretiert man die Netzwerke mit Zyklen als deterministische oder nichtdeterministe endliche Automaten, die man um ein Band wie bei der Turingmaschine erweitert, dann hat man eine Turingmaschine. Mit dieser Annahme erscheint die Äquivalenz (Netzwerke + Band $\Longleftrightarrow$ Turingmaschine) plausibel.
2. McCP-These 2: Unter der Annahme, dass gilt (Netzwerke + Band $\Longleftrightarrow$ Turingmaschine) kann man sagen, dass ein (Netzwerke + Band) ein (Netzwerk mit Zyklen $\Longleftrightarrow$ endlicher Automat) berechnen kann, da ein endlicher Automat äquivalent ist zur Menge der regulären Ausdrücke, die wiederum eine echte Teilmenge der rekursiven Mengen sind, für die gilt, dass eine Turingmaschine bei allen Inputs einer rekursiven Menge anhält.
3. McCP-These 3: Diese Aussage ist schwer zu beweisen. Sie macht einige implizite Annahmen, die wir hier wie folgt hypothetisch rekonstruieren: (i) Diejenigen Zahlen, die ein Organismus -wie der des Menschen- berechnen kann, bilden eine Teilmenge jener Zahlen, die eine Turingmaschine berechnen kann. (ii) Wenn ein Netzwerk mit Zyklen anstatt des biologischen Gehirns in den Organismus eingesetzt würde -mit Anbindung an alle Sensoren und Effektoren- dann kann es genau die gleichen Zahlen berechnen, die der Organismus auch sonst berechnen kann, und diese bilden eine Teilmenge jender Zahlen, die eine Turingmaschine berechnen kann.

Während die Interpretation der Thesen McCP-These 1-2 mit dem übereinstimmt, was heute allgemein akzeptiert wird, ist die Interpretation der These McCP-These 3 offen. Die Gleichmächtigkeit von Gehirn und Turingmaschine konnte noch nicht zweifelsfrei bewiesen werden, was nicht zuletzt auch daran liegt, dass es sich hier um eine empirische Hypothese handelt, die nicht rein formal entschieden werden kann. Die heute verfügbaren Daten über das Gehirn lassen diese These zwar immer wahrscheinlicher erscheinen, aber eine endgültige zweifelsfreie Entscheidung steht noch aus (falls sie -aufgrund der Natur der Sachlage- überhaupt jemals zweifelsfrei entschieden werden kann).