[MPlayer-cvslog] halting problems (was: Re: r26723 - in trunk: Makefile av_opts.c av_opts.h)

[Diego Biurrun]

On Thu, May 15, 2008 at 01:03:18PM +0200, Michael Niedermayer wrote:
> On Thu, May 15, 2008 at 12:30:14PM +0200, Diego Biurrun wrote:
> > On Thu, May 15, 2008 at 04:10:07AM +0200, Michael Niedermayer wrote:
> > > On Wed, May 14, 2008 at 07:15:59PM +0200, Diego Biurrun wrote:
> > > > > -- 
> > > > > 
> > > > > Awnsering whenever a program halts or runs forever is
> > > > > On a turing machine, in general impossible (turings halting problem).
> > > > 
> > > > undecidable
> > > > 
> > > > > On any real computer, always possible as a real computer has a finite number
> > > > > of states N, and will either halt in less than N cycles or never halt.
> > > > 
> > > > semidecidable
> > > > 
> > > > What were you trying to say there?
> > > 
> > > exactly what i did say.
> > > 
> > > > Any particular instance of the
> > > > halting problem is semidecidable, the general problem is not.
> > > 
> > > That exactly is false.
> > > The problem is perfectly decideable in the general sense on any real
> > > computer i could think of.
> > 
> > Imagine a (very simple) program that searches for an odd perfect number.
> > Whether such a number exists or not is an open question.  If you let
> > such a program run on any real computer, it could either
> > 
> > - output an odd perfect number or
> > - run out of resources.
> > 
> > In the latter case, the question whether the program that searches for
> > an odd perfect number halts or not has not been answered.
> 
> The error in your reasoning is the following:
> "Imagine a (very simple) program that searches for an odd perfect number"
> 
> you assume here that such a program does exist.

Sure, why wouldn't it?  It's quite a simple program.  Reminder: A
perfect number is a natural number that is the sum of its positive
divisors, i.e. 6 = 1 + 2 + 3.

> While a naive program doing that will of course only be able to search
> 2^64 numbers, one using an arbitrary precission lib could search
> 2^bits_of_mem numbers. Thus really we only know how to write a
> (very simple) program which searches for an odd perfect number < N. And that
> is perfectly decideable.

I think you misunderstand what the Halting Problem is in this context.
The question is not whether or not the *computer* halts.  The question
is whether or not the *program*, in this case the one that searches for
an odd perfect number, halts.

If we run this program on a computer and it exhausts all resources, then
we are no smarter than before.  The program could halt or not.

Maybe we are just misunderstanding each other.  It is clear that the
number of states of a computer is finite and it is possible to calculate
an upper bound for this number.  If we have a means of logging all these
states and noticing when the number of states has crossed the upper
bound (leaving aside for the moment that a human observer may not live
long enough to see that day), then of course the computer will run forever.

We will then know that this particular program will run forever on this
particular computer.  However, we have gained no insight into the
question whether or not the program halts at all.

Diego