Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!crdgw1!procyon!nielsen
From: nielsen@procyon.crd.ge.com (paul e nielsen)
Newsgroups: comp.theory
Subject: Re: Question on halting problem
Keywords: for 10 bonus points...
Message-ID: <18974@crdgw1.crd.ge.com>
Date: 26 Apr 91 21:09:51 GMT
References: <Apr.25.08.44.05.1991.23782@athos.rutgers.edu>
Sender: news@crdgw1.crd.ge.com
Organization: GE Research, Schenectady NY
Lines: 52

In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes:
>
>Turing's proof of the undecidability of the halting problem is based
>on assuming that an algorithm to decide halting existed, and then
>proving from that a contradiction. This brings up my point: Is it
>possible to define an algorithm s.t. its termination is undecidable?
>(Since I like to play with computers more than I like to play with
>theories, I'll phrase the question in terms of a "program" rather than
>an "algorithm".)
>
>For 10 points:
>
>Give the source code for a sequential program (in the language of your
>choice) such that:
>
>* The program compiles correctly and executes without errors;
>* The program does not read any input or respond to any external
>  signals;
>* It is undecidable whether the program terminates.
>
>- Steve (masticol@cs.rutgers.edu)

Here's a short program you can play with at home, if you have Common Lisp.
The decidability of its termination is based on proving Fermat's Last Theorem.

(defun fermat ()
  "Find a solution to Fermat's Last Theorem"
  (do ((a 1 (1+ a)))
      (NIL)					; Terminates when solution found
    (do ((b 1 (1+ b)))
	((> b a))				; Assume A >= B
      (do ((c a (1+ c)))			; C >= A && C >= B
	  ((=> c (+ a b)))			; C < A + B (triangle ineq)
	(do ((i 2 (1+ i))
	     (prev NIL cur)
	     (cur 0))
	    (NIL)		; Terminates when difference is increasing
	  (cond ((zerop (setf cur (abs (- (expt  c i)
					  (+ (expt a i) (expt b i))))))
		 (return-from fermat		; Halt program!
		   (format NIL "~D^~D + ~D^~D = ~D^~D" a i b i c i)))
		((and prev (>= cur prev))	; Difference increasing
		 (return)))			; Return from innermost do
	  )))))


P.S. Where can I redeem my 10 points?
--
===============================================================================
Paul Nielsen                        		          VOICE: (518) 387-5141
GE Corporate R&D Center	                               INET: nielsen@crd.ge.com 
Schenectady, NY 12345                            UUCP: uunet!crd.ge.com!nielsen