Hacker News new | ask | show | jobs
by Legend2440 823 days ago
This table is not computable. If you had this table, you could solve the halting problem by simply looking up whether the program produced an output.
1 comments

You've just restated the halting problem.

Nobody claimed that there is an algorithm to translate arbitrary programs into an equivalent lookup table. (Because that's the exact same proposition as stating that there is a program that can compute whether an arbitrary program halts when executed).

The point is: Any specific program can be translated into a lookup table. Computer programs and lookup tables are equivalent!

You claimed that computer programs are somehow "more powerful" than lookup tables. That's just plain wrong. They're exactly equivalent in "power".