Is the halting problem decidable for pure programs on an ideal computer?

Problem Detail: 

It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems that a pure program's halting on an ideal computer would be decidable through e.g. static analysis.

Is this in fact the case? If not, what are some counterexamples or papers disproving this claim?

Asked By : Jules

Answered By : Lieuwe Vinkhuijzen

Here is a proof of undecidability by reduction from the Halting problem.

Reduction: Given a machine $M$ and an input $x$, build a new Turing Machine $H$ which does not read any input, but writes $M$ and $x$ on the tape and simulates $M$ on $x$ until $M$ halts.

The behaviour of this new machine $H$ is independent of the input tape, so it is a pure Turing Machine on which only static analysis is applicable. If static analysis were sufficient, then it could show whether $H$ halts, which would show whether $M$ halts on $x$, which would solve the halting problem for impure machines, which we know is undecidable, and therefore your problem is undecidable too.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63403