Compilers as translators
A compiler takes a program written in one language and produces an equivalent program in another. A Pascal-style program becomes machine code, a high-level program becomes bytecode, and a toy language might be turned into something else entirely. The word “compiler” often suggests a big engineering project, but the central idea is simple: a function that maps programs in a source language to programs in a target language so that the translated program behaves like the original.
The concept is not limited to compilers. A transpiler converts between high-level languages. An assembler is a translator for a very low-level notation. Even an interpreter can be viewed as a translation in disguise: instead of producing a new program, it carries out the meaning of the source directly, which is the same relationship seen from the other side.
What “equivalent” means
A translation is only useful if it preserves behavior. For a source program P and its translation T(P), the usual requirements are:
- Whenever P produces some output on an input, T(P) produces the same output on that input.
- Whenever P runs forever, T(P) does too, and whenever P halts, T(P) halts.
- If P does not produce a result because it failed in some defined way, T(P) fails in a corresponding way.
Real compilers add further goals such as speed, size and readable error messages. The theory only cares about the core requirement: that the translator is correct and that it can be carried out by an algorithm. The translator itself must be a computable function that always finishes; otherwise the translation tells you nothing useful.
Why translation proves relationships between languages
Suppose there is a translator from language A into language B. Any program you can write in A can be turned into a program in B with the same behavior. So B can do at least everything A can do. In the vocabulary of expressive power, B is at least as powerful as A.
If translators exist in both directions, the languages are equally powerful, though not necessarily equally pleasant or fast. This is the basis for the claim that mainstream languages are all Turing complete in an idealized sense: they can be compiled into each other, or into a Turing machine description, and back.
The same logic produces universality results. To show that a strange new language is universal, you can write a translator from a language already known to be universal into it. Every program of the known language then has a counterpart in the new one. This is the heart of the usual recipe for completeness proofs, and one reason the proof can be short: you only need to build one translator and argue that it is correct.
A tiny example
Consider two small languages.
Language A has a single counter holding a non-negative integer, with these instructions: add one to the counter, subtract one if the counter is greater than zero, and jump to a numbered line if the counter is zero.
Language B uses a stack of symbols with push, pop and a test that checks whether the stack is empty.
A translation from A to B could represent the counter as the number of marker symbols on the stack:
- adding one pushes a marker;
- subtracting one pops a marker if the stack is not empty;
- the zero test becomes the empty-stack test;
- jumps and line numbers carry over unchanged.
Each A instruction becomes a fixed short sequence of B instructions. The translated program keeps the stack height equal to the counter value at every moment, which is the invariant that makes the translation correct. This shows that B can do whatever a one-counter language can do. A language with a single stack is not automatically able to simulate two counters, so showing power with the full strength you want takes more care.
Translating into and out of grid languages
Grid languages add an interesting twist to translation: layout. When you translate a linear program into a two-dimensional one, you must decide where each piece of code goes, and how to route the instruction pointer between pieces. The geometric side is considerable work, but conceptually it is the same: each source instruction becomes a small block, and jumps become paths. A grid compiler has to solve this layout problem on top of the usual translation. Going the other direction, from a grid language to a linear one, often means turning each cell’s behavior into a case in a big dispatch loop, much like the fetch and execute cycle of an interpreter.
Writing an interpreter and writing a compiler are related tasks, and the choice between them is partly about convenience. Anyone building interpreters will notice how closely the two tasks resemble each other.
What translation cannot do
Translation preserves what a program does, but it does not remove limits. If a source program is undecidable to analyze, its translation is too. It also cannot add power: a translator from A to B shows B is at least as strong as A, but it says nothing about whether A is as strong as B.
Efficiency may change as well. A faithful translation can make programs much slower or much larger. A language that simulates another through a long chain of encodings may be formally equivalent while being impractical, which is why the theory and everyday engineering use different measures of “good.”
Summary
Translation turns the vague question “which language is stronger?” into a concrete task: find a correct, algorithmic mapping. When one exists, it proves a precise relationship, and when mappings exist both ways, the languages share the same computational power.