Re: Halting Problem

none 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.
)>
)> 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.
)
) 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.
) 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.
)
) Thanks to all for entertaining my thought experiment.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.

Relevant Pages

  • Re: Halting Problem
    ...  Not an infinite amount of time. ... the theoretical computer running the halting problem ... His machines for the HALTS() ... in an amount of time equal-to or greater-than the amount of time it would ...
    (comp.programming)
  • 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
    ... 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)