piet@cs.ruu.nl (Piet van Oostrum) (05/31/91)
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')rockwell@socrates.umd.edu (Raul Rockwell) (06/01/91)
Piet van Oostrum:
------------------------------ test.c ------------------------------------
<same declaration of does_terminate>
main()
{
if does_terminate("test.c")
while (1);
}
------------------------------------------------------------------------
So what is the result of the command
halting test.c
?????
Segmentation fault - core dumped
;-)
Raul Rockwell