Warp wrote:
> somebody <x### [at] ycom> wrote:
>> True in that Turing machines do have unbounded memory. Of course no real
>> machine does or will.
> 
>   That doesn't make solving the halting problem any easier.

Sure it does, if you have a machine to test it on that has exponentially 
more memory than the machine it runs on.

If you have a pseudo-Turing machine with 5 states and a binary tape only 10 
symbols long, if it runs more then 5K steps, it's never going to halt.

The halting problem is specifically about Turing machines with unbounded 
memory, if that's what you mean.  (I know you know this, so I must be 
misunderstanding what you mean.)

Maybe you mean it doesn't make practical program analysis significantly 
easier to know it's only going to run on a machine with a few gigabytes of 
memory?

>   It's like the computational complexity of algorithms: Since an algorithm
> will always be run on a computer with limited resources, techincally speaking
> that means that all (terminating) algorithms are O(1).

Good thing that's not how O() is defined. :-)

-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message