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

[Diego Biurrun]

On Fri, May 16, 2008 at 02:38:39AM +0200, Michael Niedermayer wrote:
> On Fri, May 16, 2008 at 01:21:01AM +0200, Diego Biurrun wrote:
> > 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.
> 
> Our misunderstanding/disagreement is around the word "program"
> A program has no meaning outside some language which defines what constructs
> are valid and what they mean.
> 
> You can use an abstract language in which you can formulate the naive search
> for an odd perfect number up to infinity. But such a program cannot be run
> on a physical computer, the proof for this is trivial. The language requires
> the search to find a number in finite steps if one number exists no matter
> how large, but no physical computer could test arbitrary large numbers.
> Thus the "compiled" program violates the language -> There is no such thing
> as "this program on a particular physical computer".

No.  The program can have perfectly defined semantics outside of any
physical computer.  Whether any physical computer can run the program up
to termination is an entirely different question.

> You can use a down to earth language which does not gurantee infinite
> resources. In such a language you can NOT formulate the naive search
> for an odd perfect number up to infinity. You can write some approximation
> of course but thats a different thing ...

I have attached a program to output an oddPerfectNumber written in
Haskell.  The implementation of factorize is left as an exercise for the
reader.  The semantics are defined and the termination is an open
question.  There might well exist a computer some day that does not run
out of resources, but outputs an odd perfect number.

> What you do is you change your axioms silently as they fit best into the
> wanted theorem.
> 
> Either you have a program which does a search over all natural numbers
> or you do have one which searches until a hardware specific finite N.
> The first is not executable on a real computer, the second has no
> concept of "what if N is infinite".
> 
> Its simple either N is finite or N is not finite ...
> 
> A program which finds a odd perfect number if one exists
> AND
> A program which finds a odd perfect number if one exists below N
> Are 2 different things. If you want the first you must accept that its
> an abstract concept and not something a physical computer could literally
> execute.
> And the second will not neccesarily awnser your mathematical question and
> will not result in the halting problem.

There is no way to find out if the largest existing computers have
exhausted their number of states N.  Checking this would require an even
larger computer.  There is also no guarantee that you will live long
enough to see it reach N.  Thus your finite bound is just as theoretical
as an abstract definition of the halting problem.

Do not confuse the halting problem with the question whether a specific
program terminates/loops on a specific computer.  The halting problem is
not about computers, but about programs.

> What my point is, is that there should be a big red line between these
> "seriously important" CS theorems and any real computer or real program.
> Ive seen it often enough that people used such CS theorems to justify
> why some question about something which can be excuted on a real computer
> could not be awnsered. It just doesnt apply to such things.

Examples?  You seem to judge CS from what you overheard people that
obviously do not understand CS say about CS ...

Diego
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pn.hs
Type: text/x-haskell
Size: 272 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/mplayer-cvslog/attachments/20080531/f680a607/attachment.hs>