💻 computer science

Training Transformers as a Universal Computer

Dit artikel toont aan dat een kleine transformer, getraind op willekeurig gegenereerde MicroPy-programma's, kan generaliseren tot het uitvoeren van complexe, door mensen geschreven algoritmen, en zo empirisch bewijs levert dat standaard transformers kunnen fungeren als universele computers.

Oorspronkelijke auteurs: Ruize Xu, Chenxiao Yang, Yanhong Li, David McAllester

Gepubliceerd 2026-04-29

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Ruize Xu, Chenxiao Yang, Yanhong Li, David McAllester

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een zeer slimme, maar met een licht kortetermijngeheugen uitgeruste, robotassistent voor. Je wilt hem leren hoe hij complexe computerprogramma's moet uitvoeren. Het probleem is dat de robot maar een beperkt aantal stappen tegelijk kan "denken" voordat hij het begin van het verhaal vergeet. Als een programma te lang is, raakt de robot de weg kwijt.

Dit artikel presenteert een oplossing voor dat probleem. De onderzoekers bouwden een kleine, vereenvoudigde programmeertaal genaamd MicroPy en leerden een standaard AI-model (een Transformer) om te fungeren als een universele computer die elk programma in deze taal kan uitvoeren, zelfs die welke het nog nooit heeft gezien.

Hier is hoe ze dat deden, met behulp van alledaagse analogieën:

1. De Taal: MicroPy (De "Lego-set")

Bekijk MicroPy niet als een volwaardige programmeertaal zoals Python of C++, maar als een zeer strikte, vereenvoudigde set Lego-instructies.

Het bevat basisblokken voor dingen zoals "als dit, dan dat", "zoek deze waarde op" of "verander dit object".
Omdat het een vereenvoudigde versie is van een "universele" taal (een taal die theoretisch elke berekening kan uitvoeren), kan de AI, als hij deze specifieke Lego-blokken begrijpt, theoretisch alles bouwen.

2. Het Probleem: Het "Lang Verhaal"-probleem

Normaal gesproken schrijft een AI, wanneer het probeert een wiskundig probleem op te lossen of code stap voor stap uit te voeren (een methode genaamd "Chain of Thought"), elke enkele stap op.

De Analogie: Stel je voor dat je een boek leest, maar je kunt maar de laatste 10 pagina's in je hoofd houden. Als het boek 1.000 pagina's lang is, vergeet je het begin tegen de tijd dat je het einde bereikt. Je kunt het mysterie niet oplossen omdat je bent vergeten wie de schurk was in hoofdstuk 1.
In computertaal vult het "contextvenster" (het kortetermijngeheugen van de AI) zich te snel met lange berekeningen.

3. De Oplossing: PENCIL (Het "Opruimteam")

De onderzoekers gebruikten een speciale truc genaamd PENCIL. Denk aan PENCIL als een magisch "opruimteam" dat de AI helpt zijn geheugen te beheren.

Hoe het werkt: Wanneer de AI een kleine subtaak afrondt (zoals het berekenen van een getal of het voltooien van een functie), wist het PENCIL-team direct de rommelige tussenstappen uit het geheugen van de AI en houdt alleen het eindresultaat over.
De Analogie: Stel je voor dat je een complex maaltijd kookt. In plaats van elke vuile pan, steelpan en verpakking van ingrediënten op het aanrecht te houden (wat uiteindelijk de hele keuken vult), was je het vaatwerk en leg je het direct weg nadat je het hebt gebruikt. Je houdt alleen het afgewerkte gerecht op het aanrecht. Op deze manier kun je een enorm banket koken in een kleine keuken zonder dat de ruimte op raakt.
Dit stelt de AI in staat programma's uit te voeren die 60 keer langer zijn dan die waarvoor het is getraind, omdat het zijn "keukentafel" nooit rommelig laat worden.

4. De Training: Willekeurige Oefening versus Echte Tests

De onderzoekers leerden de AI niet door hem beroemde, door mensen geschreven code te tonen. In plaats daarvan genereerden ze miljoenen willekeurige, betekenisloze MicroPy-programma's.

De Analogie: Het is alsof je een student schaak leert spelen door hem te laten spelen tegen een computer die willekeurige, onzin zetten maakt. De student leert de regels van hoe de stukken bewegen en hoe ze slaan, in plaats van specifieke beroemde partijen uit het hoofd te leren.
Zodra de AI deze regels had geleerd uit de willekeurige oefening, testten ze hem op echte, door mensen geschreven programma's die daadwerkelijke dingen deden, zoals:
- Bits (binaire data) kopiëren en omdraaien.
- Grote binaire getallen optellen en vermenigvuldigen.
- Logische puzzels oplossen (SAT-problemen).

5. Het Resultaat: De Universele Computer

Het resultaat was verrassend en perfect.

De AI behaalde 100% nauwkeurigheid op alle door mensen geschreven tests.
Hoewel de testprogramma's veel langer en complexer waren dan iets dat de AI tijdens de training zag, ging hij er perfect mee om.
Het artikel beweert dat dit bewijst dat een standaard AI-model kan worden getraind om te fungeren als een universele computer. Het heeft niet alleen antwoorden uit het hoofd geleerd; het heeft de logica geleerd van hoe instructies worden uitgevoerd, waardoor het kan generaliseren naar volledig nieuwe, onbekende programma's.

Samenvatting

Kortom, het artikel laat zien dat als je een standaard AI een vereenvoudigde taal geeft om te leren en een "geheugenreiniger" (PENCIL) om hem te helpen bij het beheren van lange taken, het kan leren fungeren als een universele computer. Het kan instructies uitvoeren die het nog nooit heeft gezien en ze perfect uitvoeren, wat bewijst dat deze modellen echt kunnen leren "denken" en rekenen, en niet alleen het volgende woord voorspellen.

1. Probleemstelling

Hoewel theoretisch werk suggereert dat Transformers, uitgebreid met Chain-of-Thought (CoT), computationeel universeel zijn (in staat om Turing-machines te simuleren), bestaat er een aanzienlijke kloof tussen expressiviteit (wat ze theoretisch kunnen representeren) en leerbaarheid (wat ze daadwerkelijk kunnen leren via gradient-based optimalisatie).

Huidige uitdagingen omvatten:

Mislukte Generalisatie: Modellen worstelen met lengte-generalisatie (bijvoorbeeld het optellen van getallen die langer zijn dan die in de training zijn gezien) en compositie-generalisatie (het oplossen van nieuwe combinaties van primitieven).
Contextflesnek: Standaard CoT vereist een contextlengte van $O(T)$ , waarbij $T$ de tijdscomplexiteit van de taak is. Dit maakt training en inferentie op lange, complexe programma's binnen gebonden contextvensters onuitvoerbaar.
Gebrek aan Universeel Leren: Eerdere pogingen om neurale interpreters te trainen, vertrouwen vaak op specifieke, vooraf ontworpen functies of gespecialiseerde architecturen, en falen erin aan te tonen dat een standaard-Transformer kan leren om een algemeen, Turing-volledige taal te interpreteren.

De centrale vraag die wordt behandeld is: Kan een standaard-Transformer worden getraind om te fungeren als een universele computer, die generaliseert naar ongezette programma's en lengtes?

2. Methodologie

De auteurs stellen een raamwerk voor dat een nieuwe programmeertaal, een geheugenefficiënte uitvoeringssteunstructuur en een specifiek trainingsregime combineert.

A. MicroPy: Een Berekenbare Universele Taal

De auteurs hebben MicroPy ontworpen, een vereenvoudigde maar Turing-volledige objectgeoriënteerde programmeertaal.

Semantiek: Het vertrouwt op een kleine, eindige set ophaling (retrieval) en herbeschrijf (rewriting) regels.
- Ophaling: Opzoeken van functiedefinities, variabele bindingen of attribuutwaarden uit de context (stapelkaders of staat).
- Herbeschrijving: Het reduceren van primitieven (bijvoorbeeld IF, SEQ, LookupAttr) tot eenvoudigere expressies op basis van de huidige staat.
Structuur: Programma's bestaan uit proceduredefinities en expressies. Uitvoering omvat stap-voor-stap reductie van expressies, met beheer van mutabele staat (attributen van objecten) en stapelkaders (voor lokale variabelen).
Doel: Door deze eindige regels te leren, leert het model om elk MicroPy-programma te interpreteren, effectief fungerend als een universele interpreter.

B. PENCIL-steunstructuur: Uitvoering met Gebonden Context

Om de bottleneck van de contextlengte ( $O(T)$ ) aan te pakken, maken de auteurs gebruik van PENCIL (van Yang et al., 2025).

Mechanisme: PENCIL introduceert een reductieregel die voltooide tussenresultaten herwint. Wanneer een sub-berekening (een stapelkader) voltooid is, worden de tussenliggende redeneringsstappen gewist en wordt alleen het eindresultaat bewaard.
Complexiteit: Dit begrenst de contextlengte tot $O(S)$ (ruimtecomplexiteit) in plaats van $O(T)$ (tijdscomplexiteit).
Analogie: Het werkt als een stapeldiscipline in programmeertalen: zodra een functie retourneert, wordt zijn lokale stapelkader verwijderd, waardoor de grootte van het contextvenster beheersbaar blijft, zelfs voor langlopende programma's.

C. Generatie van Trainingsdata

Het model wordt getraind op uitvoeringssporen gegenereerd vanuit willekeurig gegenereerde MicroPy-programma's.

Twee Samplers:
1. Programma-niveau Sampler: Genereert diverse syntactische structuren via een probabilistische contextvrije grammatica.
2. Plan Sampler: Zorgt voor dekking van zeldzame runtime-configuraties (specifieke stapelskeletten en ophalingspatronen) door een doel-"plan" (stapelstructuur) te bemonsteren en een programma te compileren om dit te realiseren.
Supervisie: Het trainingsdoel is next-token prediction op stap-voor-stap uitvoeringssporen. Het model voorspelt de volgende herschrijfstap (ophaling of lokale reductie) gegeven de huidige context.
Beperkingen: Trainingsprogramma's zijn beperkt tot 128 spoorlijnen om diversiteit te garanderen zonder het model te overweldigen, terwijl evaluatie veel langere programma's test.

D. Modelarchitectuur

Architectuur: Een decoder-only Transformer (59,5M parameters) met RoPE (Rotary Position Embeddings).
Optimalisatie: Gebruik van AdamW voor embeddings en Muon voor 2D-matrixparameters.
Input: Proceduredefinitie + te evalueren expressie + Huidige Staat/Stapel.
Output: De volgende stap in het uitvoerspoor (token voor token).

3. Belangrijkste Bijdragen

MicroPy-taalontwerp: Creatie van een Turing-volledige taal met een semantiek gebaseerd op een eindige set ophalings- en herschrijfregels, wat compositie-leren faciliteert.
Empirisch Bewijs van Universeel Leren: De eerste demonstratie dat een standaard-Transformer, uitsluitend getraind op willekeurige sporen van een universele taal, kan generaliseren tot het uitvoeren van complexe, door mensen geschreven programma's die het nooit heeft gezien.
PENCIL-integratie: Succesvolle toepassing van PENCIL-steunstructuur om een Transformer in staat te stellen programma's uit te voeren met spoorlengtes tot 60x langer dan die tijdens de training zijn gezien, binnen een vast contextvenster.
Perfecte Generalisatie: Bereiking van 100% nauwkeurigheid op vastgehouden taken die bitmanipulatie, rekenkunde en logische oplossingen omvatten, wat sterke compositie- en lengtegeneralisatie bewijst.

4. Experimentele Resultaten

Het model werd geëvalueerd op vastgehouden, door mensen geschreven MicroPy-programma's die aanzienlijk langer en semantisch betekenisvoller waren dan de trainingsdata.

Geëvalueerde Taken:
- Bitmanipulatie: Kopiëren en omdraaien van bits in gelinkte lijsten.
- Rekenkunde: Binaire optelling en vermenigvuldiging (met behulp van bit-string representaties).
- Logica: SAT-verificatie en SAT-oplossing (met behulp van backtracking-zoekopdrachten).
Prestaties:
- Nauwkeurigheid: Het model behaalde 100% token-niveau nauwkeurigheid op alle taken binnen het geteste contextvenster.
- Lengtegeneralisatie: Het model voerde succesvol programma's uit met spoorlengtes tot 7.552 lijnen, ondanks dat het was getraind op programma's die beperkt waren tot 128 lijnen.
- Verdelingskloof: Er was bijna geen overlap tussen de verdeling van trainingsprogramma's en de testset, wat bevestigt dat het model de regels van uitvoering heeft geleerd in plaats van specifieke programma's te hebben gememoriseerd.
Operatie-dekking: De trainingsgenerator dekte elk operatietype dat in de testset werd gebruikt (bijvoorbeeld If, LookupVar, TailApp), waardoor het model alle noodzakelijke primitieven tijdens de training zag.

5. Betekenis en Implicaties

Universele Berekening is Leerbaar: Het paper levert sterk empirisch bewijs dat computationele universaliteit niet alleen een theoretische eigenschap van Transformers is, maar een vaardigheid die kan worden verworven via standaard next-token prediction-training op een geschikte taal.
Inductieve Bias voor Compositie: De resultaten suggereren dat Transformers, wanneer ze worden gekoppeld aan contextbeheer-steunstructuren (zoals PENCIL), een inductieve bias bezitten die goed geschikt is voor zinsstructuur en compositieve semantiek. Dit weerspiegelt de structuur van zowel programmeertalen als natuurlijke taal.
Overbrugging van de Kloof: Het werk overbrugt de kloof tussen "Neurale Computers" (die I/O-sporen leren) en formele interpreters, en toont aan dat een enkel model kan leren om een formele, Turing-volledige taal uit te voeren.
Toekomstige Richtingen: De auteurs suggereren dat dezelfde mechanismen die het leren van een programmeertaalinterpreter mogelijk maken, kunnen verklaren waarom Transformers zo effectief zijn in natuurlijke taalopgaven, aangezien beide vertrouwen op compositieve semantiek. Toekomstig werk zou dit kunnen uitbreiden tot rijkere talen en redenering zonder expliciete uitvoeringssporen.

Kortom, dit paper demonstreert dat een standaard-Transformer kan worden getraind om te fungeren als een universele computer, in staat om willekeurige programma's van een Turing-volledige taal uit te voeren met perfecte nauwkeurigheid, mits de uitvoering wordt gesteund om de context efficiënt te beheren.