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

[Michael Niedermayer]

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".

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 ...

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.

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.

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

I have often repented speaking, but never of holding my tongue.
-- Xenocrates
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/mplayer-cvslog/attachments/20080516/ef6057c1/attachment.pgp>