Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!munnari.oz.au!brolga!uqcspe!cs.uq.oz.au!matthew
From: matthew@cs.uq.oz.au (Matthew McDonald)
Newsgroups: comp.theory
Subject: Re: Question on halting problem
Keywords: for 10 bonus points...
Message-ID: <1010@uqcspe.cs.uq.oz.au>
Date: 26 Apr 91 06:40:03 GMT
References: <Apr.25.08.44.05.1991.23782@athos.rutgers.edu>
Sender: news@cs.uq.oz.au
Reply-To: matthew@cs.uq.oz.au
Organization: Computer Science Department, The University of Queensland, Brisbane, Australia
Lines: 46

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.
>
	I don't know whether or not the termination of the following procedure
is decidable, but I'll bet *you* can't decide anyway  :-).

void goldbach()
{
	int i;
	int j, k;
	int found_it;

	for (i=2; ;i += 2) {
		found_it = 0;
		for (j = 1; j <= i && !found_it; j++) {
			for (k = 1; k <= i && !found_it; k++)
				if (prime(j) && prime(k) && j * k == i)
					found_it = 1;
			if (!found_it && k == j && j == i)
				/* Got even number that's not sum of 2 primes */
				return;
		}
	}
}
	Not a very theoretical answer but you "like to play with computers
more than" you "like to play with theories" anyway. Do I get 5 points????
	
>- Steve (masticol@cs.rutgers.edu)
	Matthew.