Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!zephyr.ens.tek.com!uw-beaver!Teknowledge.COM!unix!clipper!smryan
From: smryan@clipper.ingr.com (Steven Ryan)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <1991Jun18.172115.7185@clipper.ingr.com>
Date: 18 Jun 91 17:21:15 GMT
References: <22012:Jun1205:25:0491@kramden.acf.nyu.edu> <1991Jun12.194212.21395@clipper.ingr.com> <10452.Jun1317.26.4791@kramden.acf.nyu.edu>
Organization: Intergraph Advanced Processor Division - Palo Alto, CA
Lines: 36

OOOOOO Danny you're so rough. I guess you like playing public school master.
All us bad little boys better bare our bottoms and let you flail away.

>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? It's simple to write a pda which uses no
heap. Does this mean
		pda = fsm	?

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

>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. The analyzer analyzer only uses four times times as much space as the
analyzee, but does it halt? I know, I'll build an analyzer for it. The
analyzer analyzer analyzer only uses eight times as much space as the
analyzee, but does it halt? I know, I'll build an analyzer for it. The
. . . analyzer analyzer analyzer analyzer analyzer analyzer analyzer . . .

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.
-- 
|-In compliance with DoC,-----------------------Steven Ryan--------------------|
| this posting is devoid         |              2400 Geng Road, Palo Alto, CA  |
| of all information.            |       [clipper![wyrmham!]] smryan@ingr.com  |
|-And Oliver North married William Secord/and gave birth to a little Teheran.--|