Findings of EMNLP 2026
Towards Training Transformers
as a Universal Computer
Our transformer trains on randomly generated programs and generalizes to human-written programs.
MicroPy in action
Executing a SAT solver,
one step at a time.
Find x, y, and z that satisfy every clause. Follow the search tree alongside the stack and the next completion the model is trained to predict.
¬ means NOT · ∨ means OR · ∧ means AND. A clause is satisfied when at least one literal is true.
write current variable = True check clauses at a full assignment if failure: discard branch effects retry current variable = False on success: keep the witness
Model output target · reference completion
Inspect all 1,531 exact interpreter steps
Model input · definitions + facts + current stack
Target output
View the actual MicroPy assignment-search function
The same sat_assign function used for this recorded run. eval_cnf checks the linked-list representation of the clauses; Try discards effects when an attempt returns fail_.
@mp.MicroPy
def sat_assign(var, cnf_head_, out_):
return mp.If(
mp.HasAttr(var, NEXT),
mp.Try(
mp.Seq(
mp.Assert(var, VALUE, mp.true_),
sat_assign(mp.LookupAttr(var, NEXT), cnf_head_, out_),
),
mp.Seq(
mp.Assert(var, VALUE, mp.false_),
sat_assign(mp.LookupAttr(var, NEXT), cnf_head_, out_),
),
),
mp.Try(
mp.Seq(
mp.Assert(var, VALUE, mp.true_),
mp.If(
eval_cnf(cnf_head_, mp.LookupAttr(cnf_head_, VALUE)),
mp.Assert(out_, VALUE, mp.true_),
mp.fail_,
),
),
mp.Seq(
mp.Assert(var, VALUE, mp.false_),
mp.If(
eval_cnf(cnf_head_, mp.LookupAttr(cnf_head_, VALUE)),
mp.Assert(out_, VALUE, mp.true_),
mp.fail_,
),
),
),
)Replay of a real reference-interpreter run, with exact prompt/completion pairs. This replay is not live neural-model inference. Only visited assignments are marked; unexplored branches remain gray.
The idea
Trained on random programs.
Tested on human-written programs.
MicroPy is a small, computationally universal language with function calls, recursion, objects, and mutable attributes. A conventional interpreter supplies traces of randomly generated programs. A standard decoder-only transformer learns to predict the next local retrieval or rewrite, then executes held-out human-written programs.
This is a route toward an executable mental model: internally predicting how code changes a world of objects and facts. The paper tests program execution; using this interpreter inside a broader reasoning agent is a motivation for future work.
01 / The pieces that must compose
Read effects. Write effects.
Keep the right facts.
An effect is an ordered record of changes to object attributes. The current answer depends on which writes remain live—and which write came last.
A long whole-program execution can reuse familiar small steps. A long single-step effect merge still requires the model to copy and combine a long sequence correctly. Coverage of one does not automatically provide coverage of the other.
02 / Training data
Choose the stack you need.
Build a program that reaches it.
Random programs provide broad syntax coverage. The plan compiler deliberately constructs the runtime configurations that random sampling can miss.
Program sampler
Pretraining-like roleSample general MicroPy code with a PCFG. Execute it and learn from the resulting steps.
Plan compiler
Post-training-like roleSpecify a stack skeleton, bindings, and effects. Compile code that reaches that shape; retain the matched step.
These labels describe the samplers’ roles. The reported training mixes both sources; this is not a claim of a separate two-stage training schedule.
Target / retrieve a recently written fact
[call] Eff(a.value = True)
[call] LookupAttr(a, value)The plan specifies both the operation and the fact that must be available in the live effects.
Construct / lead execution to that state
Seq(Assert(a, value, true_),
LookupAttr(a, value))The first expression writes the fact. The second reads it while the effect is on the stack.
Supervise / the matching step
input: … LookupAttr(a, value)
output: ⇒ Eff(empty) True [ret]Vary outer frames, bindings, and distractor effects around the intended retrieval.
Simplified semantic illustration of plan-directed construction. Exact interpreter serialization is available in the playground below.
Which execution patterns does the paper target?
Retrieval leaves: LookupVar, LookupAttr, and TailApp with concrete environment / effect requirements. These put the correct binding or object fact among other context entries.
Continuation frames: Seq, If, Try, Env, and Eff. The paper additionally documents long pre-TailApp effect writes and zero-argument call boundaries as coverage gaps.
Source: paper §4.1 and appendix “Distribution-Shape Failure Examples”. This inventory does not establish an independent ablation for each pattern.
03 / Try MicroPy
A program in.
An execution you can inspect.
Edit the program, run it, and step through the stack. The output shows both the result and the changes to object attributes.
Final object attributes
PENCIL
The model emits a completion ending in [ret]. PENCIL replaces the completed [call] segment with its result, keeping the effects needed for the next step.
The trained transformer learns these targets. This playground uses the Python reference interpreter, not a model checkpoint.
1 · Input: current stack
2 · Output: predicted rewrite target
3 · After PENCIL reduction
Full serialized model input
What can I type?
Use Obj("a"), Attr("value"), true_, false_, unit_, and fail_; compose Seq, If, Equal, Assert, LookupAttr, HasAttr, and Try. Define recursive functions with def and one return expression. Set program = … to choose the entry point.
MicroPy is its own language, not general Python. This demo accepts its constructor syntax and stops at 2,000 steps or a 10-second execution limit. The first custom run downloads the Python runtime; bundled examples can be inspected immediately.
Resources
Interpreter and training code
Synthetic execution traces and evaluation programs