[cap-talk] C vs. Safety

[Tony Bartoletti]

At 05:07 PM 8/7/2008, you wrote:
>On Thu, 2008-08-07 at 14:10 -0700, Tony Bartoletti wrote:
> > At 01:29 PM 8/7/2008, Valerio Bellizzomi wrote:
> > 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) ...
> >
>
>I don't know what an "extended" integer is... perhaps this is the reason
>for the following, however.

(simply "arbitrary sized" as you suspected.)


>Surely (assuming arbitrary precision integer arithmetic) termination
>here can be proved as follows.
>
>Unwind the loop once to arrive at
>
>K=N
>if (k>1){
>    if (k%s){
>       k = (3*k+1)/2;
>    }else{
>       k = k/2;
>    }
>}
>
>// invariant: k is even or k == 1

False.

Let N = 7:
  then k becomes (3*7 + 1)/2 = 11.
  then k becomes 17,
  then k becomes 26,
  then k becomes 13, ...



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