> Maybe I'm missing a big obvious one, but there's something about programmable systems that they are necessarily unable to infer or deduce the output of a prog

> Maybe I'm missing a big obvious one, but there's something about programmable systems that they are necessarily unable to infer or deduce the output of a program beyond a certain complexity without first running it. Yep, this is Rice's Theorem. If we have a particular program P which outputs a certain value, there is an infinite set of programs of the form 'C; P;' which first run some arbitrary code 'C' and then run P. The Halting Problem is undecidable, so we can't always tell whether code 'C' will halt or not; and hence whether we'll move on to executing P or not. More generally, Rice's Theorem applies to any non-trivial property of the input/output function implemented by a program. A non-trivial property means that at least one program has that property and at least one program doesn't. Being a property of the 'input/output function implemented by a program' avoids implementation details like 'runs for at least 10 steps'. The Halting Problem is semi-decidable: if we just run the given program until it halts then return 'HALTS', we will always return the correct answer when given a program which halts. This doesn't completely solve the Halting Problem, since we will not return 'NON-HALTING' when given a non-halting program (we will just run forever). Wolfram calls this "computational irreducibility": that the only way to predict the behaviour of a Turing-complete system is to simulate it; or, equivalently, any formula that tells us what will happen on the Nth step will, necessarily, involve calculating what happens on the (N-1)th step, the (N-2)th step, and so on back to the first step.