Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site amdahl.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!bellcore!decvax!decwrl!sun!amdahl!krs
From: krs@amdahl.UUCP (Kris Stephens)
Newsgroups: net.puzzle
Subject: Loop termination proof problem.
Message-ID: <1283@amdahl.UUCP>
Date: Fri, 15-Mar-85 06:07:26 EST
Article-I.D.: amdahl.1283
Posted: Fri Mar 15 06:07:26 1985
Date-Received: Sun, 17-Mar-85 02:31:24 EST
Distribution: net
Organization: Amdahl Corporation, Sunnyvale CA
Lines: 28

Okay,  here's a problem program written in REXX,  but it can be done in
any language;  it's the idea that counts:

   /* PROBLEM */
   say "Enter a positive integer:"   /* Type prompt                    */
   parse external i                  /* Read number from terminal      */

   do until i=1                      /* Start loop                     */
      if i/2 = trunc(i/2)            /* Q. Is "i" even?                */
       then i = i/2                  /* A. Yup. Divide by 2            */
       else i = 3*i + 1              /* A. No. Multiply by 3 and add 1 */
      say i                          /* Type it for user               */
   end                               /* End of loop                    */

   say "Terminated at 1."            /* Report completion              */
   exit                              /* And leave                      */

The challenge  is to  prove that  this program  will terminate  for all
positive integer values of "i".  I suspect that it's unprovable, and so
am re-reading Godel-Escher-Bach to find out (Does that make sense?).

I've done a bunch  of work on this,  and if folk are  interested,  I'll
append what I've got so far.

-- 
Kris Stephens     (408-746-6047)                 {whatever}!amdahl!krs
     [The opinions expressed above are mine, solely, and do not    ]
     [necessarily reflect the opinions or policies of Amdahl Corp. ]