[Theory] Halting problem

[Norbert Nemec]

On 10/10/2010 09:16 PM, %u wrote:
>> Basically: because 1GB=infinity for all purposes of logical reasoning.
> No no no! :D
> If you'd left out logical it would have been just fine :D
> I'm not even going to give ridiculous logical proof with this assumption.. no I
> will not..
> ..
> assume inf is 1GB.. No!

Sorry, my wording was extremely poorly chosen.

What I meant was: if you start any logical reasoning based on the 
"finite state space" of a real computer, this approach is very likely to 
be of little practical value for a real world problem.

More explicitely: a brute force solution of the halting problem is 
indeed theoretically possible for a finite machine, but it scales 
exponentially in the memory size, resulting in a run time which is large 
compared to anything that you could reasonably call "finite".