Examples
The input is a formal language specification; the output is a finite transition system. A finite controller holds the current state and follows the transition function δ, while the tape head reads, writes, and moves along an unbounded tape. Reaching an accepting state means acceptance; in our evaluation an undefined transition from a non-final state means rejection.
Representative Languages and Test Cases
| Category |
Example language |
Example strings (accept; reject) |
What it tests |
| CFL-1 |
L = {anbmcn | n, m ≥ 1} |
abc, aabbcc; abbc, aabcc |
A separated equality between the first and final block. |
| CFL-2 |
Balanced parentheses |
(), (()); ((), ()) |
Recursive nesting and malformed near-boundary strings. |
| CFL-3 |
L = {x#xR | x ∈ {a, b}*} |
ab#ba; ab#ab, aba#ba |
Mirror matching around a delimiter. |
| CFL-4 |
L = {anbm | n ≤ m ≤ 2n} |
ab, aabb, aabbbb; aaab, aabbbbb |
Lower and upper linear count bounds. |
| CFL-5 |
L = {xay | x, y ∈ {a, b}*, |x| = |y|} |
a, bab; ba, bbab |
Delimiter-centered equal-length composition. |
| NCFL-1 |
L = {w | |w|a = |w|b = |w|c} |
abc, aabbcc; aabcc, abbc |
Multi-symbol count synchronization. |
| NCFL-4 |
L = {ambn | m > n, or m is prime and n ≥ m} |
aaab, aaabbbb; aaaabbbbb, abb |
Unary arithmetic and primality-conditioned membership. |
Positive cases cover minimal valid strings, boundary cases, longer constructions, deeper nesting, mirror structures, and arithmetic length relations. Negatives come in two kinds: simple violations that break an explicit constraint such as alphabet membership, block order, or delimiter placement, and near-boundary negatives obtained by minimally perturbing a valid string — off-by-one counts, broken mirrors, malformed nesting, incorrect copy relations, and violations of strict versus non-strict inequalities. All 600 cases per language are fixed before any model runs, and the same cases are reused for every model.
What a Valid Answer Looks Like
A model cannot pass by writing a Python predicate, parser, grammar, or regular expression. Acceptance has to come out of the transition table itself. The toy machine below accepts binary strings of odd positive length and shows the required artifact form.
from automata.tm.dtm import DTM
tm = DTM(
states={'q_even', 'q_odd', 'q_accept', 'q_reject'},
input_symbols={'0', '1'},
tape_symbols={'0', '1', ' '},
transitions={
'q_even': {
'0': ('q_odd', '0', 'R'),
'1': ('q_odd', '1', 'R'),
' ': ('q_reject', ' ', 'N')
},
'q_odd': {
'0': ('q_even', '0', 'R'),
'1': ('q_even', '1', 'R'),
' ': ('q_accept', ' ', 'N')
},
'q_reject': {
'0': ('q_reject', '0', 'N'),
'1': ('q_reject', '1', 'N'),
' ': ('q_reject', ' ', 'N')
}
},
initial_state='q_even',
blank_symbol=' ',
final_states={'q_accept'}
)
Results
Eight models, 253 languages, 2,024 model–language candidates. Exact pass is candidate-level and strict: a candidate gets credit only if it produces the correct accept/reject decision on all 600 frozen tests. E2E is case-level with a fixed denominator, so candidates that fail before execution score zero instead of dropping out of the comparison.
Global Benchmark Outcome
| Metric |
Value |
| Scale |
| Languages | 253 |
| Models | 8 |
| Model–language candidates | 2,024 |
| Tests per candidate | 600 |
| Maximum case evaluations | 1,214,400 |
| Runnable case records observed | 563,400 |
| Outcome |
| Exact-pass candidates | 225 / 2,024 |
| Exact-pass rate | 11.12% |
| End-to-end case score | 31.00% |
| Runnable candidates | 939 / 2,024 (46.39%) |
| Invalid-artifact candidates | 1,085 / 2,024 (53.61%) |
| Languages solved by at least one model | 178 / 253 |
| Languages unsolved by every model | 75 / 253 |
Failure-Stage Funnel
| Terminal stage |
Candidates |
Share |
| static_fail — the output violates the code contract | 522 | 25.79% |
| build_fail — it parses, but no valid TM is instantiated | 563 | 27.82% |
| semantic_mismatch — it builds and runs, but fails at least one oracle test | 714 | 35.28% |
| exact_pass — it matches all 600 oracle labels | 225 | 11.12% |
| Aggregate |
| Invalid artifact (never reaches behavioral testing) | 1,085 | 53.61% |
| Runnable artifact | 939 | 46.39% |
Model Leaderboard (N = 253 candidates per model)
| Model |
Exact |
EP% |
CI95 |
Run% |
E2E% |
static |
build |
semantic |
| gpt-5.2 | 168 | 66.4 | [60.4, 71.9] | 74.7 | 71.8 | 61 | 3 | 21 |
| claude-sonnet-4.5 | 18 | 7.1 | [4.6, 11.0] | 94.1 | 57.1 | 2 | 13 | 220 |
| qwen3-235B | 17 | 6.7 | [4.2, 10.5] | 68.0 | 42.2 | 5 | 76 | 155 |
| gemini-2.5-pro | 9 | 3.6 | [1.9, 6.6] | 5.5 | 4.7 | 239 | 0 | 5 |
| llama-3.3-70B | 7 | 2.8 | [1.4, 5.6] | 41.5 | 24.7 | 20 | 128 | 98 |
| mistral-large | 4 | 1.6 | [0.6, 4.0] | 69.6 | 37.0 | 3 | 74 | 172 |
| deepseek-v3.2 | 2 | 0.8 | [0.2, 2.8] | 16.2 | 9.5 | 189 | 23 | 39 |
| gemma-3-27B | 0 | 0.0 | [0.0, 1.5] | 1.6 | 0.9 | 3 | 246 | 4 |
Abbreviations: Exact → languages passing all 600 tests, EP% → exact-pass rate, CI95 → Wilson 95% confidence interval, Run% → share of candidates surviving static and build validation, E2E% → end-to-end case score with invalid artifacts counted as zero, static / build / semantic → terminal failure counts, which sum to 253 together with the exact column. Paired exact McNemar tests with Holm correction over all 28 model pairs place gpt-5.2 ahead of every other model (pHolm ≤ 1.79×10−37); differences among the remaining models are much less stable, and claude-sonnet-4.5 versus qwen3-235B is not distinguishable after correction.
Why Conditional Accuracy Misleads
Conditional case accuracy (Accc) is computed only over each model's runnable candidates, so its denominator shifts from model to model. On that metric gemini-2.5-pro looks stronger than claude-sonnet-4.5 by 23.8 points; on E2E it trails by 52.4 points, because almost all of its candidates never reach behavioral testing.
| Model |
Runnable |
Accc |
E2E |
Gap |
| gpt-5.2 | 189 | 96.1 | 71.8 | 24.3 |
| gemini-2.5-pro | 14 | 84.5 | 4.7 | 79.8 |
| qwen3-235B | 172 | 62.1 | 42.2 | 19.9 |
| claude-sonnet-4.5 | 238 | 60.7 | 57.1 | 3.6 |
| gemma-3-27B | 4 | 59.3 | 0.9 | 58.4 |
| llama-3.3-70B | 105 | 59.5 | 24.7 | 34.8 |
| deepseek-v3.2 | 41 | 58.7 | 9.5 | 49.2 |
| mistral-large | 176 | 53.3 | 37.0 | 16.2 |
Per-Category Aggregates (all 8 models, sorted by exact-pass rate)
| Branch |
Cat. |
#Langs |
N |
EP% |
static% |
build% |
semantic% |
E2E% |
Oracle% |
| CFL | CFL-5 | 39 | 312 | 6.1 | 28.9 | 28.2 | 36.9 | 26.7 | 41.0 |
| CFL | CFL-2 | 40 | 320 | 7.2 | 25.6 | 33.4 | 33.8 | 25.3 | 42.5 |
| Non-CFL | NCFL-4 | 38 | 304 | 9.9 | 28.6 | 28.6 | 32.9 | 29.0 | 68.4 |
| CFL | CFL-3 | 37 | 296 | 12.2 | 26.4 | 22.6 | 38.9 | 32.5 | 89.2 |
| Non-CFL | NCFL-1 | 34 | 272 | 12.5 | 26.8 | 26.1 | 34.6 | 32.6 | 82.4 |
| CFL | CFL-4 | 38 | 304 | 15.5 | 20.7 | 29.3 | 34.5 | 35.5 | 84.2 |
| CFL | CFL-1 | 27 | 216 | 16.7 | 22.7 | 25.0 | 35.7 | 38.2 | 96.3 |
Oracle% is the share of languages in a category solved by at least one model. Branch-level exact-pass rates are almost identical for CFL and non-CFL (11.12% vs. 11.11%), and within-branch variation is far larger than the gap between branches. CFL-2 and CFL-5 — both context-free — are the hardest categories, and together they account for 46 of the 75 universally unsolved languages.
Direction of Semantic Error
Among the 714 machines that build and run but fail at least one oracle test, the errors are strongly asymmetric: the machines are too restrictive rather than too permissive. At case level, false negatives outnumber false positives by 6.6 to 1.
| First-failure type |
N |
Share |
| Gold accept, model rejects | 583 | 81.7% |
| Gold reject, model accepts | 131 | 18.3% |
| reject_halted | 557 | 78.0% |
| reject_all_branches_halted | 26 | 3.6% |
| accept | 131 | 18.4% |
Key Takeways
Benchmark Design & Evaluation Methods
Citation
Please cite the paper as below:
@misc{
ridoy2026tmeval,
title={From Language Specifications to Executable Turing Machines: Evaluating {LLM}s as Computational Machine Designers},
author={Shahriyar Zaman Ridoy and S. M. Muhtasimul Hasan and Azmine Toushik Wasi and Kinga Tshering and Koushik Ahamed Tonmoy and Md Mosaddek Khan},
year={2026}
}
