🤖 machine learning

A PyTorch Library of Turing-Complete Neural Networks

Dieser Beitrag stellt eine PyTorch-Bibliothek vor, die Turingmaschinenbeschreibungen in exakte, trainingsfreie neuronale Netzwerksimulationen unter Verwendung zweier unterschiedlicher Architekturen kompiliert: eines auf Wei et al. (2021) basierenden Transformers und eines auf Siegelmann und Sontag (1995) basierenden rekurrenten Netzwerks.

Ursprüngliche Autoren: Jonathan Bates

Veröffentlicht 2026-05-12

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jonathan Bates

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben ein Rezept für einen sehr spezifischen, komplexen Tanz. Normalerweise würde man einem Roboter diesen Tanz beibringen, indem man ihm die Bewegungen tausende Male zeigt und es ihm ermöglicht, durch Versuch und Irrtum zu „lernen". Doch was wäre, wenn man dem Roboter einfach einen Bauplan geben könnte, der besagt: „Wenn du Schritt A siehst, führe Bewegung B aus; wenn du Schritt C siehst, führe Bewegung D aus", und der Roboter könnte den Tanz beim allerersten Versuch perfekt ausführen, ohne jemals geübt zu haben?

Genau das leistet dieser Aufsatz, nur dass er anstelle eines Tanzes ein neuronales Netzwerk (eine Art künstliche Intelligenz) dazu bringt, sich wie eine Turing-Maschine zu verhalten – das theoretische „Gehirn" hinter allen modernen Computern.

Hier ist die Aufschlüsselung, wie sie es getan haben, unter Verwendung einfacher Analogien:

1. Die große Idee: „Kompilieren statt Trainieren"

Die meisten heutigen KI-Systeme sind wie ein Schüler, der für eine Prüfung lernt, indem er ein Lehrbuch immer wieder liest. Dieser Aufsatz stellt ein Paket (eine Sammlung von Werkzeugen für Programmierer) vor, das eher wie ein Übersetzer funktioniert. Man gibt ihm die „Regeln" eines Computerprogramms (die Turing-Maschine), und es schreibt sofort die „Gewichte" (die internen Einstellungen) eines neuronalen Netzwerks so, dass das Netzwerk die Regeln von Anfang an perfekt „kennt". Kein Lernen, kein Raten, kein Training erforderlich. Es ist „durch Konstruktion korrekt".

2. Das Werkzeugset: Logik von Grund auf aufbauen

Um diesen Übersetzer zu bauen, mussten die Autoren zeigen, wie ein neuronales Netzwerk grundlegende Mathematik und Logik betreiben kann, genau wie ein Taschenrechner.

Die Steine (Logikgatter): Sie zeigten, wie man einfache „Schalter" (wie UND, ODER, NICHT) innerhalb des Netzwerks baut. Denken Sie an diese als winzige Lichtschalter, die sich je nach bestimmten Bedingungen ein- oder ausschalten.
Der Bauplan (DNF): Sie organisierten diese Schalter in ein bestimmtes Muster (wie einen Flussdiagramm), das jede Regel beschreiben kann, die der Computer befolgen muss.
Der Taschenrechner (Addierer): Sie bauten einen digitalen Addierer innerhalb des Netzwerks. Dies ermöglicht es der KI, hoch- oder herunterzuzählen, was für einen Computer essenziell ist, um zu wissen, wo er sich auf seinem „Band" (Speicher) befindet.

3. Zwei verschiedene Wege, die Maschine zu bauen

Der Aufsatz bietet zwei verschiedene „Baupläne" (Architekturen), um diese Regeln in eine funktionierende KI zu verwandeln.

Bauplan A: Der Transformer (Der „Super-Leser")

Diese Version basiert auf einer modernen KI-Architektur namens Transformer (derselbe Typ, der auch in Chatbots verwendet wird).

Funktionsweise: Stellen Sie sich einen Bibliothekar vor, der ein massives Geschichtsbuch besitzt. Jedes Mal, wenn der Computer einen Zug machen muss, schaut der Bibliothekar auf alles zurück, was vorher passiert ist, um den richtigen Hinweis zu finden.
Der Trick: Es wird ein spezieller „harter Aufmerksamkeits"-Mechanismus verwendet. Anstatt vage zu raten, welches vergangene Ereignis wichtig ist, wirkt er wie ein Laserpointer, der sich genau auf ein bestimmtes Stück Information aus der Vergangenheit fixiert, um seine Entscheidung zu treffen.
Das Ergebnis: Es simuliert den Computer schrittweise und erinnert sich perfekt an die Historie des Bands und den aktuellen Zustand.

Bauplan B: Das rekurrente Netzwerk (Der „Tellerstapel")

Diese Version basiert auf älteren Forschungen aus den 1990er Jahren.

Funktionsweise: Anstelle eines langen Bands betrachtet diese Maschine den Speicher als Stapel von Tellern (wie ein federbelastetes Tablett in einer Cafeteria).
Die magische Mathematik: Die Autoren verwenden einen cleveren mathematischen Trick namens Cantor-Menge. Stellen Sie sich vor, Sie quetschen einen unendlichen Stapel Teller in eine einzige Zahl zwischen 0 und 1.
- Einen Teller hinzufügen (Pushen) ist wie das Multiplizieren dieser Zahl.
- Einen Teller entfernen (Poppen) ist wie das Dividieren dieser Zahl.
Der Haken: Da dies darauf beruht, unendliche Information in eine einzige Zahl zu quetschen, ist es sehr anfällig für Rundungsfehler. Es funktioniert in der Theorie perfekt, aber in einem echten Computer wird die Zahl bei zu vielen gestapelten Tellern zu unübersichtlich, um sie genau abzulesen.

4. Warum das wichtig ist (laut dem Aufsatz)

Die Autoren behaupten nicht, dass dies Ihr Telefon schneller macht oder Krankheiten heilt. Stattdessen bieten sie einen Beweis des Konzepts und ein Werkzeugset:

Eine Brücke: Sie verbindet die Welt der reinen Mathematik (Logik und Turing-Maschinen) mit der Welt der neuronalen Netzwerke.
Eine Referenz: Sie gibt Forschern ein perfektes, ausführbares Beispiel zum Studium.
Stabilitätsprüfung: Da das Netzwerk perfekt von Hand gebaut wurde, können Wissenschaftler nun testen, was passiert, wenn man die Einstellungen leicht „anstößt" (wie das Hinzufügen von Rauschen oder das Feinabstimmen). Zerbricht die perfekte Maschine oder bleibt sie stabil?

Zusammenfassung

Betrachten Sie diesen Aufsatz als Fabrikhandbuch. Es sagt nicht nur „KI kann Mathematik". Es sagt: „Hier sind die exakten Montageanweisungen, um eine Maschine zu bauen, die Mathematik perfekt ausführt, unter Verwendung nur der Rohmaterialien neuronaler Netzwerke." Es beweist, dass man, wenn man die Regeln kennt, die Maschine sofort bauen kann, ohne sie beibringen zu müssen, wie sie lernt.

Technische Zusammenfassung: Eine PyTorch-Bibliothek Turing-vollständiger neuronaler Netze

Problemstellung

Während die theoretische Literatur längst nachgewiesen hat, dass neuronale Netze Turingmaschinen (TMs) simulieren können – insbesondere durch rekurrente Netze (Siegelmann & Sontag, 1995) und Transformer mit harter Aufmerksamkeit (Pérez et al., 2021; Wei, Chen, & Ma, 2021) – besteht eine signifikante Lücke zwischen mathematischen Beweisen, die Gewichtungsmatrizen spezifizieren, und ausführbaren, konkreten Implementierungen. Bestehende Beweise beruhen häufig auf unendlicher Präzision oder abstrakten Konstruktionen, die in Standard-Frameworks des Deep Learnings schwer zu realisieren sind. Dieser Beitrag adressiert das Bedürfnis nach einer „konkreten, ausführbaren Referenz", die die symbolischen und neuronalen Domänen verbindet, indem sie eine Turingmaschinen-Beschreibung direkt in ein neuronales Netz mit festen, interpretierbaren Gewichten kompiliert, das kein Training erfordert.

Methodik

Die Autoren stellen ein PyTorch-Paket vor, das neuronale Netze aus einer gegebenen TM-Übergangsfunktion ( $\delta$ ) und einer Menge von Endzuständen konstruiert. Die Kompilierung erfolgt durch eine Hierarchie von Komponenten, die sicherstellt, dass der Vorwärtsdurchlauf des Netzes exakt einen Schritt der spezifizierten Maschine implementiert. Zwei unterschiedliche Architekturen werden implementiert, die jeweils ein anderes theoretisches Ergebnis realisieren:

1. Kernkomponenten

Der Aufbau beruht auf der Konstruktion komplexer Logik aus grundlegenden, durch ReLU aktivierten Gattern:

Boolesche Logik: Der Beitrag zeigt, wie ReLU-Netze elementare Gatter (UND, ODER, NICHT, XOR) implementieren und diese zu Schaltkreisen in disjunktiver Normalform (DNF) zusammensetzen.
Übergangsfunktion: Die endliche Nachschlagetabelle $\delta$ wird als zweischichtiger DNF-Schaltkreis realisiert, wobei ein verstecktes Neuron für jedes Zustands-Symbol-Paar existiert.
Binäre Arithmetik: Ripple-Carry-Addierer, konstruiert aus Halb- und Volladdierern, werden verwendet, um die Kopfposition zu aktualisieren (Inkrementieren oder Dekrementieren binär kodierter Ganzzahlen).
Positionale Nachschlage: Mechanismen harter Aufmerksamkeit (approximiert über Softmax mit hoher Temperatur) führen exakte positionale Nachschlagen auf dem Bandverlauf und der ursprünglichen Eingabe durch, indem binäre Schlüssel-Abfrage-Vektoren abgeglichen werden.

2. Architektur A: WCM21 (Transformer-basiert)

Basierend auf der Konstruktion von Wei, Chen und Ma (2021) handelt es sich um einen Encoder-Decoder-Transformer:

Encoder: Speichert das initiale Band als feste Matrix mit One-Hot-Symbolkodierungen und binären Positionsindizes.
Decoder: Verfolgt autoregressiv den Berechnungsverlauf. Jeder Schritt umfasst eine Pipeline aus:
1. Übergang: Eine Feedforward-Schicht implementiert die TM-Übergangsfunktion via DNF.
2. Arithmetik: Eine Kette von Ripple-Carry-Addierern aktualisiert die Kopfposition.
3. Verlaufswiedergewinnung: Self-Attention-Schichten führen eine binäre Suche über den Decoder-Verlauf durch, um den letzten Schreibvorgang an der aktuellen Kopfposition zu finden.
4. Bandwiedergewinnung: Cross-Attention liest das ursprüngliche Bandsymbol vom Encoder.
5. Symbolzusammenstellung: Eine prioritätsbasierte Feedforward-Schicht wählt das korrekte Symbol aus (letzter Schreibvorgang > ursprüngliches Band > leer).
Präzision: Verwendet binäre Positionskodierung, um Bruchteile bei Aufmerksamkeitswerten zu vermeiden, was die Implementierung mit endlicher Präzision (float32) ermöglicht.

3. Architektur B: SS95 (Rekurrent-basiert)

Basierend auf Siegelmann und Sontag (1995) reformuliert dieser Ansatz die TM als Stapelmaschine:

Kodierung: Stapel werden als einzelne rationale Zahlen innerhalb einer Cantor-Menge kodiert (unter Verwendung der Basis $b=4$ und des Parameters $\rho=1/2$ ).
Operationen: Stapeloperationen (push, pop, peek) werden als lineare oder stückweise lineare Funktionen des kodierten Wertes realisiert, manipuliert durch Matrixmultiplikationen und gesättigte lineare Aktivierungen ( $\sigma(x) = \text{clamp}(x, 0, 1)$ ).
Implementierung: Zwei Versionen werden bereitgestellt:
- Eine explizite 4-Schichten-Pipeline-Version.
- Eine 1-Schichten „Echtzeit"-rekurrente Version.
Präzision: Die 1-Schichten-Variante ist anfällig für Rundungsfehler (verstärkt durch die Basis $b$ ), erfordert float64 und begrenzt die Anzahl zuverlässiger Operationen im Vergleich zur 4-Schichten-Variante.

Hauptbeiträge

Konstruktive Darstellung: Eine systematische Herleitung, wie ReLU-Netze boolesche Schaltkreise realisieren, fortschreitend von einzelnen Gattern über DNF-Formeln bis hin zu binären Addierern.
Ausführbare Implementierung: Ein vollständiges PyTorch-Paket, das eine TM-Beschreibung entgegennimmt und ein Modell mit Gewichten ausgibt, die direkt aus der Maschinendefinition spezifiziert sind. Kein Training ist erforderlich; das Netz ist „durch Konstruktion korrekt".
Open-Source-Grundlage: Der Codebase dient als Basislinie für die Untersuchung der Stabilität konstruierter Lösungen unter Störungen und gradientenbasiertem Fine-Tuning und adressiert die Lücke zwischen theoretischer Existenz und praktischer Optimierung.

Ergebnisse und Fähigkeiten

Das Paket simuliert erfolgreich Turingmaschinen, demonstriert anhand eines ausgeglichenen Klammerprüfers.

WCM21: Für eine Maschine mit 6 Zuständen, 5 Symbolen und 100 Schritten hat das Modell eine Embedding-Breite von 59. Es arbeitet mit numerischer Exaktheit in float32, da alle Zwischenwerte in $\{0, 1\}$ verbleiben.
SS95: Die 4-Schichten-Version ist für typische Eingaben stabil. Die 1-Schichten-Version, obwohl näher an der ursprünglichen theoretischen Konstruktion, zeigt nach etwa 8 Pop-Operationen eine Verschlechterung der Präzision aufgrund der Akkumulation von Rundungsfehlern in der Cantor-Kodierung.

Bedeutung und Behauptungen

Der Beitrag positioniert sich nicht als Vorschlag für neue Anwendungen oder als Behauptung überlegener Leistung gegenüber trainierten Modellen, sondern als Grundlegendes Werkzeug für Interpretierbarkeit und theoretische Verifikation.

Durch Konstruktion bedingte Interpretierbarkeit: Im Gegensatz zu Netzen, die via Gradientenabstieg trainiert werden, wo Neuronen permutiert oder verflochten sein können, hat jedes Gewicht in diesen konstruierten Netzen einen bekannten, interpretierbaren Zweck (z. B. ein spezifisches Gatter, ein spezifisches Bit des Addierers).
Überbrückung von Theorie und Praxis: Die Arbeit schließt die Lücke zwischen abstrakten Beweisen der Turing-Vollständigkeit und ausführbarem Code und liefert eine konkrete Referenz für die „symbolisch-neuronale Brücke".
Zukünftiger Nutzen: Die Autoren schlagen vor, dass die Modelle als Initialisierungen für die Untersuchung der Verlustlandschaft um konstruierte Lösungen dienen, insbesondere zur Untersuchung, wie viel Gewichtsveränderung die Simulation tolerieren kann und ob Fine-Tuning Abkürzungen liefert, die von der allgemeinen Konstruktion übersehen wurden.

Der Beitrag kommt zu dem Schluss, dass diese Konstruktionen zwar theoretisch fundiert und praktisch ausführbar sind, sie jedoch die inhärenten Kompromisse zwischen theoretischer Turing-Vollständigkeit und praktischer numerischer Stabilität hervorheben, insbesondere im Kontext der Arithmetik mit endlicher Präzision.