Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!vtserf!creatures!csgrad!lavinus
From: lavinus@csgrad.cs.vt.edu
Newsgroups: comp.theory
Subject: Re: Question on halting problem
Keywords: for 10 bonus points...
Message-ID: <1161@creatures.cs.vt.edu>
Date: 26 Apr 91 15:48:26 GMT
References: <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> <1991Apr26.135918.8607@m.cs.uiuc.edu>
Sender: usenet@creatures.cs.vt.edu
Reply-To: lavinus@csgrad.cs.vt.edu ()
Organization: Virginia Tech Computer Science, Blacksburg, VA
Lines: 20

Hi!

My personal favorite is the following:

proc foo(n)
   while (n > 1)
      if (even(n)) n = n div 2
      else         n = 3 * n + 1
end

As far as I know, it has never been proven that this program halts for all
n.  Evidence to the contrary would be quite welcome (BTW, I believe the
credit for this problem is due to Ulam).

Joe
--
_________________________________ \ ___________________________________
 Joseph W. Lavinus, Virginia Tech  \   email: lavinus@csgrad.cs.vt.edu
 1204-A University Terrace         /\  phone: (703) 552-0241
 Blacksburg, VA  24060            /  \        (703) 231-5853