[cap-talk] C vs. Safety

[Tony Bartoletti]

At 01:29 PM 8/7/2008, Valerio Bellizzomi wrote:

> >>> Hmm... isnt static safety as unsolvable as the famous halting problem?
> >>> That is the question: does program p ever do anything unsafe?
> >>
> >> It is certainly NOT as unsolvable as the halting problem.
> >>
> >You are correct.
> >If we imagine the possible controlflow of an program as an graph then
> >clearly programs that have indeterminable loops (example: while (true)
> >{ doSomething(); })
> >are cyclic graphs while programs that dont have such loop are acyclic
> >graphs.
> >But that is whole another oiltanker of worms.
>
>The while (true) guarantees that the loop runs forever, it is not
>indeterminable, we know that it is an infinite loop.

I think:

   while( value == TRUE ) do_something(&value);

is what was intended...

Mathematicians would love to know if there exists an (extended) 
integer N > 1 for which the following procedure fails to exit:

   k = N;
   while( k > 1 )
   {
         if( k%2 ) // k is ODD
                 k = (3*k+1)/2;
         else    k = k/2;
   }
   exit();

... or a proof that no such N exists (the process ALWAYS exits) ...



Tony Bartoletti 925-422-3881 <azb at llnl.gov>
Lawrence Livermore National Laboratory
Livermore, CA 94551-9900