Path: utzoo!attcan!uunet!know!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!apple!agate!linus!linus!bs From: bs@linus.mitre.org (Robert D. Silverman) Newsgroups: comp.theory Subject: Re: 3n + 1 problem Message-ID: <121439@linus.mitre.org> Date: 27 Sep 90 15:41:55 GMT References: <1990Sep21.212241.21613@athena.mit.edu> <1290@fornax.UUCP> Reply-To: bs@faron.UUCP (Robert D. Silverman) Organization: The MITRE Corporation, Bedford MA Lines: 26 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 Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"