Re: Scripting

[Steve Baker <sjbaker1@airmail.net>]

Jorrit Tyberghein wrote:

> First, note that the halting problem applies only to infinite computers (turing
> machines). In practice computers are finite (finite memory states) so the
> halting problem is solveable (but inpractical) in practice.

This is getting a bit off-topic - but whilst it's technically true,
it's not OK to say that the halting problem is solvable for finite
machines.  Providing the computer that's analysing the program to
see if it halts is ALSO finite and of comparable size/complexity to
the one that will run the program you are analysing, then the halting
problem is unsolvable.

Remember the 'classic' proof:

  Question: Can you write a function (P) that will examine the code
  for any arbitary function (Q) and tell you whether for some arbitary
  input, it'll eventually terminate or whether it'll loop forever?

  Answer: NO.

  Reason:  If you could write 'P' then you could call it in another
  function that looks like this:

   void q (some_input)
   {
    if ( p(some_input) == WILL_HALT )
      while ( 1 ) /* Do Nothing */ ;
    else
      return ;
   }

  ...then you just feed 'q' into itself.  If P says that Q will
  halt then Q will simply get stuck in that 'while' loop - and
  if P says it'll run forever then it'll halt - hence P doesn't
  work for an input like Q and hence you cannot write P.

Well, so long as any hypothetical working version of P is small
enough to run on your finite computer for any input that's also
small enough to run on that computer...THEN it's also going to
be possible to run Q on that same computer and prove that for
programs that this computer can run, the halting problem cannot
be solved by by any program that this computer can run.

Now, if you are allowed to talk about finite computers - then
you need to find one that can run P but not Q.  Since Q is only
a few bytes longer than P, that's not a realistic restriction.
It means that you can only possibly solve the halting problem
for all programs that are smaller than the smallest possible
decision making program.  It's no use padding out P to make
it bigger (call that 'P2') because Q can run the lean-mean
version of P and still be undecidable.

Godel's number is not infinite.

There is an analogous problem to the Halting Problem - which
is the issue of whether you can analyse two functions and
prove that for the same inputs, they'll always generate the
same outputs.  That's also something that it's possible to
prove is impossible.

Hence, if you have a perfect program that works 100% correctly,
you can't prove that some other program produces the exact same
results.  This means that you can't prove whether a program works
or not - in the general case.

----------------------------- Steve Baker -------------------------------
Mail : <sjbaker1@airmail.net>   WorkMail: <sjbaker@link.com>
URLs : http://www.sjbaker.org
       http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net
       http://prettypoly.sf.net http://freeglut.sf.net
       http://toobular.sf.net   http://lodestone.sf.net