|
![](/i/fill.gif) |
Warp wrote:
> somebody <x### [at] y com> 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
|
![](/i/fill.gif) |