[MPlayer-cvslog] r26723 - in trunk: Makefile av_opts.c av_opts.h

[Michael Niedermayer]

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:
> > On Tue, May 13, 2008 at 02:29:23PM +0200, Michael Niedermayer 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.
> It only becomes undecidable on computers with unbounded (infinite) resources.
> (=turring machines)
> 

> If you would attempt to apply the common proof of turrings halting problem to
> a real computer then you would simply hit a stack overflow and get a
> perfectly consistant awnser ...

More precissly if we assume T(p,i) to be the function deciding if p(i)
halts and T() being an emulator running p(i) for N+1 cycles. And
p(i) being the nasty
    if(T(p,i))
        1: goto 1;
    else
        return;

then calling T(p,i) to find out about p(i) creates an emulator which then
emulates if(T(p,i)) but that itself creates another emulator and so forth
Eventually resources be it stack or heap will run out and an emulated p(i)
will fail (=halt due to out of memory) this will cause the previous T(p,i)
call to return 1 (halts) the next previous T(p,i) return 0 (does not halt)
due to the explicit 1 goto 1, and so on until the first T(p,i) returns.

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

It is not what we do, but why we do it that matters.
-------------- 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/20080515/e9fe4fb3/attachment.pgp>