Easy questions and hard questions
Some questions about a grid program are simple to answer. How many cells does the program use? Does the character at row 3, column 5 equal a particular instruction? Does the source text contain a given instruction anywhere? These questions are about the text, and a program can answer them by reading the file.
Other questions are about behavior: what happens when the program runs. Does it ever stop? Does it ever print a given character? Will the instruction pointer ever visit a particular cell? Do two programs always produce the same output? For a language that is Turing complete, many of these have no general solution, meaning that no single program can answer them correctly for every grid program given to it.
The root problem
All of these inherit their difficulty from the halting problem. The reasoning pattern is called a reduction: assume you have a tool that answers question Q for every program, and use it to build a tool that solves halting. Since halting cannot be solved, the tool for Q cannot exist either.
Here is a sketch for the question “will the instruction pointer ever reach cell X?” Given any program P that you want to test for halting, change it so that whenever P would halt, it first steers the pointer to cell X, and so that cell X is not otherwise used. Then P halts if and only if the modified program reaches X. A reachability checker would therefore tell you whether P halts. Because that is impossible in general, so is the checker.
In a language where the end of the program is simply the pointer reaching a stop instruction, this edit is natural: the stop instruction is the special cell.
Questions that are undecidable for a universal grid language
Provided the language is universal, with unbounded memory, the following are typically undecidable in general:
- Halting: does the program stop on this input?
- Reachability: will the pointer ever visit a given cell? This is the heart of identifying dead code, and a perfect detector is impossible in general.
- Output questions: will the program ever print a particular character, or ever print anything?
- Equivalence: do two programs produce the same output for every input?
- Self-modification effects: will a write ever change a given cell, a question made harder by self-modifying code, where the program rewrites the grid it runs on.
- Stack questions: will the stack ever grow past a certain size, or will it ever underflow? Interpreter authors worry about stack underflow in practice, but predicting it ahead of time is the hard part.
Notice that these all ask about what happens during runs, over all possible inputs and unlimited time.
Rice’s theorem in one paragraph
A general result, named after Henry Gordon Rice, captures the pattern. It says that any nontrivial property of the function a program computes is undecidable. “Nontrivial” means some programs have the property and some do not. “Property of the function” means it depends on what the program does and not on how it is written. For instance, “the program outputs the number 7 on input 0” is a property of behavior and is undecidable in general, while “the source contains the instruction for printing” is a property of text and is easy.
The theorem does not say that every question is hopeless. It says that no single method can get all programs right on any question about behavior.
What you can still do
Undecidability is a limit on perfect, general answers. It leaves a lot of room for useful partial ones.
- Run it with a limit. You can simulate a program for a fixed number of steps and report whether it halted within that budget. This is a decision procedure for a different, bounded question. It is how most test harnesses work.
- Conservative analysis. A tool can mark a cell as definitely reachable, definitely unreachable, or unknown. Following the pointer along straight paths and through simple turns can prove many cells reachable, and cells that no path can enter can be flagged. The unknown category is where undecidability lives.
- Restrict the language. If you forbid self-modification, limit the number of steps, or bound memory, the questions can become decidable. A program with bounded memory has finitely many configurations, so you can in principle check them all, although the number may be too large to enumerate in practice.
- Test and trace. For a particular program, tracing by hand or with a tool, as in a trace visualizer, can answer behavioral questions for the specific inputs you care about. That is not a general decision method, but it is often all you need.
- Prove things about specific programs. People verify individual programs with human reasoning. The limit is on automating all of them with one method.
An example
Take a small program whose loop runs until a computed value reaches a particular condition, and suppose the value follows an iteration with no known pattern. Whether the loop ever exits might be unknown to anyone. This is not a failing of the tool; for some iterations, it is an open mathematical problem. Asking a tool to settle every such loop is asking for something no one knows how to do, and the halting theorem says that for the general case it cannot be done at all.
Takeaway
For a universal grid language, text questions are easy, and behavior questions are generally undecidable. When building debuggers, optimizers or linters for such languages, expect approximations, timeouts and “I can’t tell” answers. They are an honest response to a real limit.