krs@amdahl.UUCP (Kris Stephens) (03/15/85)
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. ]ndiamond@watdaisy.UUCP (Norman Diamond) (03/18/85)
> 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 */ > > The challenge is to prove that this program will terminate for all > positive integer values of "i". I suspect that it's unprovable... > -- Kris Stephens It's been an open problem in pure mathematics for several years. A similar problem with around 17 variables was proven undecidable. I don't follow such things though. -- Norman Diamond UUCP: {decvax|utzoo|ihnp4|allegra}!watmath!watdaisy!ndiamond CSNET: ndiamond%watdaisy@waterloo.csnet ARPA: ndiamond%watdaisy%waterloo.csnet@csnet-relay.arpa "Opinions are those of the keyboard, and do not reflect on me or higher-ups."