Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!mcsun!hp4nl!alchemy!piet
From: piet@cs.ruu.nl (Piet van Oostrum)
Newsgroups: comp.lang.misc
Subject: HALTING PROBLEM
Message-ID: <1991May31.130751.12364@cs.ruu.nl>
Date: 31 May 91 13:07:51 GMT
Sender: piet@cs.ruu.nl (Piet van Oostrum)
Reply-To: piet@cs.ruu.nl (Piet van Oostrum)
Organization: Dept of Computer Science, Utrecht University, The Netherlands
Lines: 60

The discussion of the halting problem (which I have not completely
followed) introduced a lot of redundant arguments. What I have seen of it
did not address the fundamental problem.

Generally if you have a class of programs (= a language) there are two
possibilities:

1. The programs are very simple, but in that case the language is too
simple to write a program that can detect whether an arbitrary program in
the language will halt. (Spreadsheets come to mind as an example, although
some spreadsheet packages might include undecidable programs).

2. Complicated programs are possible, but the the problem cannot be solved
at all.

Now suppose someone claimed to be able to write a C program that can detect
whether an arbitrary C program will terminate. For simplicity I will assume
no input (you can always code the input as string constants in the program).

If you want you can substitute another programming language.

It should be possible to recode the program as follows:
--------------------------- halting.c -------------------------------------
<lots of declarations>

int does_terminate (char* prog)
{ /* returns 1 if the program on file PROG terminates, otherwise 0 */
...
}

main(int argc, char **argv)
{
/* any decent programmer knows how to write this */
}
------------------------------------------------------------------------

Now I write the following program on test.c:

------------------------------ test.c ------------------------------------
<same declarations as above>

<same declaration of does_terminate>

main()
{
	if does_terminate("test.c")
		while (1);
}
------------------------------------------------------------------------

So what is the result of the command

halting test.c

?????
-- 
Piet* van Oostrum, Dept of Computer Science, Utrecht University,
Padualaan 14, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands.
Telephone: +31 30 531806   Uucp:   uunet!mcsun!ruuinf!piet
Telefax:   +31 30 513791   Internet:  piet@cs.ruu.nl   (*`Pete')