Re: Halting Problem
- From: Willem <willem@xxxxxxxxxxxxxx>
- Date: Wed, 1 Apr 2009 20:05:11 +0000 (UTC)
) 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
) 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.
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 !
- Prev by Date: Re: Halting Problem
- Next by Date: Re: Halting Problem
- Previous by thread: Re: Halting Problem
- Next by thread: Re: Halting Problem