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

[Michael Niedermayer]

On Sat, May 31, 2008 at 02:58:33PM +0200, Diego Biurrun wrote:
> 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.  

Nothing you said contradicts what i said, so that "no" makes no sense.


> The program can have perfectly defined semantics outside of any
> physical computer. 

yes, thats what i called "an abstract language"


> Whether any physical computer can run the program up
> to termination is an entirely different question.

of course


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

We did not discuss about "open questions" but about decideability, that is
about the existence of questions which are proofably not awnserable.
They do exist under the right set of axioms but these axioms contradict
any real computer.

The factorization of the 14th fermat number for example is also an open
question but perfectly decideable, i can even write a program which on
a real computer would find a factor given enough time.


> There might well exist a computer some day that does not run
> out of resources, but outputs an odd perfect number.

Yes, you have an abstract language in which you can write the mathematical
problem (maybe that haskel program qualifies i do not know). For this we
cannot just apply the generic test about it halting or not.
But and that is what i said over and over again, you CAN NOT run this on
a computer. A computer can execute an approximation of this but never
a program that is un or semidecidable.


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

When one is out of arguments one changes the subject ...
What i was discussing is that the halting problem does not arise on a real
computer. This has nothing to do with the existence of problems which need
too many finite steps too solve in ones life or with ones equipment.
the key difference is finite vs. non finite.
I can understand that CS people do not realize that there is a difference
but it is very significant, large and finite is very different from
countably infinite which is again not the same as non countably infinite.


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

More precissely the halting problem is about programs one cannot execute on
any real computer.
These things are of large importance in math, they are irrelevant for
writing programs one plans to run on a real computer.


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

try google


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

I know you won't believe me, but the highest form of Human Excellence is
to question oneself and others. -- Socrates
-------------- 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/20080601/500bf7f7/attachment.pgp>