nand@athena.mit.edu (Nand M Mulchandani) (09/22/90)
Hi ! When I was taking my automata theory course at Cornell University, we discussed an undecidable problem which can be stated as the following : 'n' is a positive integer. if n is odd, make n = 3 * n + 1. if n is even, divide by 2. Question(s) : (maybe not exact) Does n always -> 0 ? If it does, in how many steps ? My question is : is the correct statement of the problem ? and : Has a solution been found ? Thanks in advance ! ------------------------------------------------------------------------------- Nand M. Mulchandani Department of Computer Science 630 Stewart Avenue Cornell University Ithaca, New York 14850 v2rx@vax5.cit.cornell.edu 607.273.0101 Sloan School of Management 49 Grove Street E52-504 Somerville, Massachusetts 02144 Massachusetts Institute of Technology 617.623.5550 nand@athena.mit.edu 617.253.0276 -------------------------------------------------------------------------------
mahajan@fornax.UUCP (Sanjeev Mahajan) (09/22/90)
In article <1990Sep21.212241.21613@athena.mit.edu>, nand@athena.mit.edu (Nand M Mulchandani) writes: > Hi ! > > When I was taking my automata theory course at Cornell University, we > discussed an undecidable problem which can be stated as the following : > > 'n' is a positive integer. > if n is odd, make n = 3 * n + 1. > if n is even, divide by 2. > I fail to understand in what sense this problem is undecidable. Has it been proven that it cannot be decided under some standard axioms of number theory? Sanjeev
nachum@m.cs.uiuc.edu (09/27/90)
The problem is unsolved (rather than unsolvable). See J. Recreational Math. 21(2), pp. 120-3, 1989, for a recent paper and references on the topic.
bs@linus.mitre.org (Robert D. Silverman) (09/27/90)
In article <1290@fornax.UUCP> mahajan@fornax.UUCP (Sanjeev Mahajan) writes: :In article <1990Sep21.212241.21613@athena.mit.edu>, nand@athena.mit.edu (Nand M Mulchandani) writes: :> Hi ! :> :> When I was taking my automata theory course at Cornell University, we :> discussed an undecidable problem which can be stated as the following : :> :> 'n' is a positive integer. :> if n is odd, make n = 3 * n + 1. :> if n is even, divide by 2. :> : :I fail to understand in what sense this problem is undecidable. Has it been :proven that it cannot be decided under some standard axioms of number theory? What is probably meant is that the computational procedure to decide if a given integer has the property that the sequence terminates at 1 is NOT primitive recursive. Otherwise, I have no idea. -- Bob Silverman #include <std.disclaimer> Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"