Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!snorkelwacker.mit.edu!paperboy!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <22012:Jun1205:25:0491@kramden.acf.nyu.edu>
Date: 12 Jun 91 05:25:04 GMT
References: <31051@dime.cs.umass.edu> <k3ZN38w164w@mantis.co.uk> <1991May28.204434.16396@netcom.COM>
Organization: IR
Lines: 26

In article <1991May28.204434.16396@netcom.COM> doug@netcom.COM (Doug Merritt) writes:
> I don't see why all that stuff is even being discussed; like I pointed out
> the other day, even determining halting for self-contained C programs (no
> malloc, no clock dependency, etc) is impossible,

There does not exist a single self-contained C program which will, all
by itself, determine the halting status of *every* self-contained C
program.

However, for any given *size* (including program size and memory use) of
self-contained C program, there exists a self-contained C program which
will determine the halting status of every self-contained C program
under that size. Therefore ``determining halting for self-contained C
programs'' is quite possible.

In fact, it's rather easy to construct the program with approximately
twice the given size, plus a fixed amount of housekeeping. So
``determining halting for self-contained C programs'' is not only
possible, it's practical.

In fact, it's rather easy.

Now, Doug, would you like to explain on what basis in fact or fiction
you decided to call this ``impossible''?

---Dan