Invisible wrote:
> The idea is that if you had some super-machine that could somehow decide 
> whether any given Turing machine halts for a given input, you would 
> still be unable to tell whether this brand new machine halts for a given 
> input - using exactly the same proof as the original halting problem.

That's possible. But it certainly isn't obviously true. If the 
super-computer isn't programmed in the usual way, or if (for example) it 
can execute an infinite number of instructions in finite time, or if it 
can travel back in time, or etc, I expect you'd have to think hard about 
whether that gets around the technique the halting problem proof uses.

If your super-computer cannot, for example, have its programs 
represented as input to itself (i.e., you can't create a universal 
super-computer), then the halting problem isn't even *defined* for that 
type of computer.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message