Orchid XP v8 wrote:
> But even given infinite time and memory, a computer *still* can't solve 
> the Halting Problem though. Even theoretically. Don't ask me why...


Here's the idea.  Assume we have a function halts(P,i), which takes a 
function P and returns true of P(i) halts and false otherwise.  Then 
write the following function, D:

function D(i) {
	if halts(i,i) {
		while true
	} else {
		return 0
	}
}

Note that since, mathematically, be consider all programs as integers 
(for example their compiled binary form), the line halts(i,i) is ok 
since we can interchange programs and integers to our heart's desire.

Now, when happens if we try to compute halts(D,D)?

(I'll leave this to work out for yourself, as it's a good exercise)


Once you groked this, note that although the halts function is perfectly 
well defined mathematically, we've just showed that it's impossible to 
ever program, and therefore it is not a computable function.  You can of 
course, program a halts function that works perfectly well on a subset 
of all inputs, but you can't write to to determine the answer for all 
possible programs.

Post a reply to this message