Lambda calculus and register machines compute the same functions, so what does that equivalence not promise?

## What the equivalence states Two models of computation are **equivalent** when each can simulate the other, so the set of functions computable in one is exactly the set computable in the other. Lambda calculus has no store, no instruction counter and no tape; it has terms and one rewriting rule that substitutes an argument into a body. A register machine has a handful of unbounded counters and two or three instructions. A tape machine has a tape and a head. They look nothing alike, and they compute exactly the same functions, because you can write an interpreter for any of them inside any other. That convergence is the content of the **Church-Turing thesis**: every function that can be computed by a mechanical procedure at all is in this one class. It is a thesis, not a theorem, because one side of it — *effectively calculable by a mechanical procedure* — is an informal notion. You cannot prove a formal statement equal to an informal one; you can only accumulate evidence, and every formalism proposed for a century has landed in the same class. ## What it is silent about | The equivalence fixes | The equivalence says nothing about | |---|---| | Which functions are computable at all | How many steps either model takes on a given input | | That a simulation exists in each direction | How expensive that simulation is | | That neither model computes something the other cannot | How much storage a computation needs | | That both are limited by the same outer boundary | How many symbols a programmer must write | | — | Whether the model can perform input, output or timing at all | The right slogan is that equivalence is about **reach, not cost, and not comfort**. ## Where engineers misread it - **"Equivalent means comparable performance."** No. A simulation can cost any amount; the equivalence puts no ceiling on the overhead, and analysing that overhead is a separate, resource-bounded question. - **"A model with more built-in operations is more powerful."** No. Adding operations that were already expressible changes convenience, not the computable class. That is why a model with two instructions can match one with two hundred. - **"A model with no mutable state cannot be complete."** No. Rewriting a term is a perfectly good way to carry state; the state lives in the term. - **"Since all languages are equivalent, the choice does not matter."** The choice matters enormously — for how long the program takes, how much you write, what tooling can check, and what the runtime lets you touch. None of that is what the word *equivalent* is about. - **"The thesis is a proved fact about physical devices."** It is a claim about what mechanical procedures can compute. Physical proposals so far change the cost of computing things in the class, not the class itself. ## Why the distinction earns its keep at work The practical payoff is in reading claims correctly. When somebody says a configuration format "is as powerful as a real programming language", they are making the computability claim, and it is usually true and usually not the point. The consequential claim is the other one: an evaluator for a complete model has no static bound on its own work, and that is a property you feel in production as a render that never returns. Conversely, when somebody argues a restricted format cannot possibly do the job because it is "less powerful", ask which function they actually need computed. Most of the time the task is a bounded transformation over data that is already present, which a deliberately incomplete model handles and can bound. The symmetric error is to treat a restriction as free. Dropping general recursion for iteration over a finite collection genuinely removes functions from what the format can express, and if a user's task needs one of them, they will get it back by generating the format from somewhere else. The honest statement is a trade, priced on both sides: you give up part of the computable class, you get back the ability to bound evaluation by inspecting the input. ## The one-sentence version Equivalence tells you where the outer wall is. It tells you nothing about how far apart two points inside the wall are, or how long the walk takes.