Ryan, the answer is definitively YES.
Contrary to the first answer, the halting problem does not prove anything. In fact, Ryan, what you're suggesting proves the halting problem wrong does not apply to real digital computers, and I've used this very example as a proof of it before.
In a deterministic digital system (i.e. a program running on real digital hardware), the number of possible states is finite, and therefore all possible states are enumerable.
The exact amount of memory required for the hash would be:
(2)*(program state size)*(number of initial states)
The initial state would be your hash key, and final state would be the hash value, and then you'd have a key/value pair for each initial state.
For an operating system, the "program state size" is 2^(total gigabits of memory across all system devices). Obviously, such a large, general purpose program would require an impractical amount of memory to hash, and would not be useful anyway, since the system is self-referencing/irreducibly complex (i.e. next user input depends on previous system output).
Explanation:
This is highly useful, because if you index every possible initial state and associate it with the terminating state, you would effectively bring the running time of ANY PROGRAM to zero! Any by zero I mean a very fast O(1) running time -- the time it takes to look up the terminating state (if it terminates).
Running a program, starting from each of all possible states, will provide a kind of state map showing cycles. The halting problem is therefore solved, because there are only three (actually four collapsing to three) possibilities given any possible initial state:
- The program will reenter a previously encountered state (since the initial state), before exhausting all possible states, and therefore logically loops forever.
- The program reaches a state identified as "terminating" before it has a chance to reenter a previously encountered state or exhaust all possible states (since the initial state).
or 4. The simplest program will start from an initial state, will enter all possible states exactly once, and then has no choice but to (3) halt or (4) reenter a previously encountered state and loop forever.
for (int i = 0; true; i++); //i will reach max-value, roll over back to zero, at which point it will have reentered the initial state
So, basically, your index could be described like this:
- For each initial state, there is exactly one or zero terminating states.
In other words, for each initial state, the program either reaches a terminating state or
reenters a state already encountered since the initial state and cycles endlessly.
So, for any program running on deterministic digital hardware, it is absolutely possible (but often not practical) to determine all its states and whether it halts or loops forever.
- The practicality depends solely on how many valid initial states you have (which you can reduce drastically with input constraints), and how feasible it is to take the time to run the program for each of them to termination and store the resulting state in the hash table.
Besides forcing any program's running time an O(1) operation, other uses of capturing state include the save-state function in game console emulators and the hibernate feature of computers (although not a perfect restoration of state, since some system memory must be used for the code that restores the state and some memory may never be stored (e.g. GPU memory)).
What this proves is that any program can be represented by a hash table.
Any program can be represented by an initial-to-final state-transition map.
All programs can be simplified to one big function with a massive memory-footprint!