Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!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: <10452.Jun1317.26.4791@kramden.acf.nyu.edu>
Date: 13 Jun 91 17:26:47 GMT
References: <1991May28.204434.16396@netcom.COM> <22012:Jun1205:25:0491@kramden.acf.nyu.edu> <1991Jun12.194212.21395@clipper.ingr.com>
Organization: IR
Lines: 47
X-Tone: Nasty

In article <1991Jun12.194212.21395@clipper.ingr.com> smryan@clipper.ingr.com (Steven Ryan) writes:
> In article <22012:Jun1205:25:0491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> >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.
> Not all programs have an a priori space/time bounds.

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.

> Your conclusion
> therefore only applies to bounded programs.

No shit. That's what ``for any given *size*'' means: it's a *bound*.
(``Welcome to Mr. Rogers' Neighborhood. Can you say `bound'? B-O-U-N-D.
Bound. Very good, boys and girls. This is a bound.'')

> You have no proof that unbounded
> programs do not exist.

Sure I do. Computers have finite memory. To determine halting for an IBM
PC in some state, I need merely hook up another IBM PC and a bit of
extra hardware, and run both machines a bit slower than usual. To
determine halting for a given language environment, the interpreter or
compiler need only duplicate its memory and do a bit of housekeeping.
This is eminently practical.

And, by the way, here's a bit of elementary logic: Even if unbounded
programs ``exist'' in one sense or another (certainly not in the real
world), that would not affect the validity of my statements, since I
quantified them only over the set of self-contained C programs, all of
which are bounded.

So, Stevie, what does your claim have to do with what I said? As your
mother told you: If you aren't contributing to the discussion at hand,
shut the fuck up.

> >In fact, it's rather easy.
> Perhaps you should spend a little time study the math you so easily dismiss.

Ahahahaha. That's cute. For someone who's just made a fool out of
himself, Stevie, you've got a good sense of humor, you know?

---Dan