Re: Halting Problem

On Apr 1, 2:20 pm, none <n...@xxxxxxxxx> wrote:
Willem wrote:
You're confusing 'infinite' with 'unbounded'.

Adding two unbounded numbers takes an amount of time that's dependent
on the magnitude of the numbers.  Not an infinite amount of time.

[...]

I would go a step back and claim that, to make the halting problem
decidable, the theoretical computer running the halting problem
software must be orders of magnitude more powerful than the
theoretical computer that is running the program under investigation.

And that is what Turing worked on. His machines for the HALTS()
program were the same functionality as the program under test.

To me, that's cheating.  If *you* get a certain memory to compute if
a program halts or not, then *that program* should get that also.

Well, I don't mean to restrict the "target" program to having finite
memory, only that it must operate on finitely-large values.  This is a
reasonable restriction.

Turing did not bother with that restriction.


However, I think that your point about "infinite" versus "unbound" has
found the hole in my logic.  One could create a type of variable that would
only consume the number of bits necessary to store its current value.  This
type of variable is "legal" in the sense that you can actually use it to do
things, like math.  But, it can take on an infinite number of states, and
therefore the halts() function could run indefinitely without producing a
result.

I concede!

But I do take something away from this discussion.  It's probably already
obvious to most, though.  What I understand now is that the halting problem
is only a "problem" when there are infinities involved.  So for any program
that you *could actually write*, I can write a program that will tell you
whether or not it will actually halt.  This seems like a useful conclusion.

yes. Turing was the first to do it.
 
The downside is that in many cases, my "halts()" program could only do so
in an amount of time equal-to or greater-than the amount of time it would
take to simply run the target program and see whether or not it halts.

And that is exactly the conclusion Turing proved.

Thanks to all for entertaining my thought experiment.

It was an interesting discussion. Immensely appropriate for this
group.
Thanks,
Ed
.

Relevant Pages

  • Re: Halting Problem
    ... on the magnitude of the numbers. ... Not an infinite amount of time. ... a program halts or not, then *that program* should get that also. ...
    (comp.programming)
  • Re: Halting Problem
    ... Not an infinite amount of time. ... )> I would go a step back and claim that, to make the halting problem ... )> a program halts or not, then *that program* should get that also. ...
    (comp.programming)
  • Re: Halting Problem
    ... the theoretical computer running the halting problem ... theoretical computer that is running the program under investigation. ... a program halts or not, then *that program* should get that also. ... in an amount of time equal-to or greater-than the amount of time it would ...
    (comp.programming)
  • Re: does sqrt(2) exist in CM?
    ... > the oracle for the halting problem would need to have actually infinite ... > amount of information. ...
    (comp.theory)
  • Re: does sqrt(2) exist in CM?
    ... > the oracle for the halting problem would need to have actually infinite ... > amount of information. ...
    (sci.math)