Recognizing a formal language does not imply the ability to construct the computation that decides it. We operationalize this distinction as an executable benchmark for language-model reasoning: given a formal-language specification, an LLM must synthesize a deterministic or nondeterministic Turing machine that decides the language. We introduce TMEval, a benchmark of 253 language specifications across 7 structural categories spanning context-free and non-context-free phenomena. Each language includes 600 oracle-labeled membership tests, and every output is evaluated as an executable artifact rather than a textual response. Our pipeline enforces a strict output contract, validates machine construction, executes each buildable machine, and assigns one of four outcomes: static_fail, build_fail, semantic_mismatch, or exact_pass. Across eight LLMs, 2,024 model–language candidates, and up to 1,214,400 behavioral evaluations, only 11.12% exactly pass all tests. More than half fail before execution, over one-third implement the wrong language, and 75 languages remain unsolved by all systems. Failure depends less on the context-free/non-context-free boundary than on the operational structure required to realize the specification. TMEval reveals a substantial gap between formal-language recognition and machine-checked symbolic construction. TMEval is available at https://turing-machineeval.github.io/.