Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!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: <4457.Jun2021.35.1991@kramden.acf.nyu.edu>
Date: 20 Jun 91 21:35:19 GMT
References: <1991Jun12.194212.21395@clipper.ingr.com> <10452.Jun1317.26.4791@kramden.acf.nyu.edu> <1991Jun18.172115.7185@clipper.ingr.com>
Organization: IR
Lines: 46

In article <1991Jun18.172115.7185@clipper.ingr.com> smryan@clipper.ingr.com (Steven Ryan) writes:
> >Since you obviously weren't paying attention: ``Self-contained C
> >program'' was defined by Doug to mean one that used neither malloc()
> >nor an unpredictable external input.
> (1) Is recursion also prohibited?

In any reasonable computational model with a reasonable definition of
``size'', unbounded non-tail recursion implies unbounded space.

> (2) Now that you've demonstrated all kinds of wonderful things about
> `self-contained C programs' can you give some examples of this class?

Sure: A program which integrates a fluid flow field over a 10000x10000
grid. A graph manipulation program. A program which tests a given number
for primality. A program which finds the next billion zeros of the
Riemann zeta function. Have you forgotten the derivation of the word
``computer''?

> cat? cp? Not wc unless you're going to restrict the size of the input.
> Or does predictable input mean bounded size? I guess no exabyte tape
> drives this semester.

Predictable input means that you can replace all input statements with a
bounded set of coroutines which supply that input. It does not imply
``finite input'', which more precisely might mean ``the n'th read() will
return 0 for some n''; an infinite stream of x's is perfectly
predictable. Figure out the rest for yourself.

> >Sure I do. Computers have finite memory. To determine halting for an IBM. . .
> >. . .This is eminently practical.
> (3) Of course, how stupid of me, this is soooo obvious. Let's assume your
> analyzer uses twice as much space (speak dirty to me: say bytes) as the
> analyzee. But does the analyzer halt? I know, I'll build an analyzer for
> it.

Don't be stupid. The analyzer will always halt, because the original
computer either enters a loop (in which case the analyzer detects the
loop) or itself halts (in which case the analyzer halts too).

> Dan, you sexy programmer, you. I guess all goosebumpy just thinking about
> how you've solved the halting problem. And you only need infinite space.

Are you babbling because you were lost somewhere in the evolutionary
tree, or because you simply don't know what you're talking about?

---Dan