Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!samsung!zaphod.mps.ohio-state.edu!swrinde!ucsd!ucbvax!bloom-beacon!mit-eddie!uw-beaver!ubc-cs!fornax!mahajan
From: mahajan@fornax.UUCP (Sanjeev Mahajan)
Newsgroups: comp.theory
Subject: Re: 3n + 1 problem
Message-ID: <1290@fornax.UUCP>
Date: 21 Sep 90 23:37:41 GMT
References: <1990Sep21.212241.21613@athena.mit.edu>
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 20

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