Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!uunet!stanford.edu!unix!clipper!smryan
From: smryan@clipper.ingr.com (Steven Ryan)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <1991Jun21.221831.23692@clipper.ingr.com>
Date: 21 Jun 91 22:18:31 GMT
References: <10452.Jun1317.26.4791@kramden.acf.nyu.edu>
Organization: Intergraph Advanced Processor Division - Palo Alto, CA
Lines: 77

In article <4457.Jun2021.35.1991@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>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.

Golly. I would have never thought of that of myself. Thanks.

Do you permit recursion and temporary files in your self-contained C
program?

>> (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''?

Oh, I get it now. Any program with fixed size input is equivalent to a FSM.
Wow. That's a really important result. Are you going to write about a paper
on this?

What about an n*n grid where n is not known when the program is coded?
What n+e graph manipulator when n and e are not known when the program....
A program that tests any number for primality?
The next m zeros?

Computer? Compter? I reckon so. (Inside joke for our Dutch and German friends.)

>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.

Well, the coroutines have to be fixed size to compile. If you're serious about
bounded recursion and space, that means the only unbounded inputs are
type 3 languages. Wow, another important result. It only takes a FSM to
recognise a type 3 language.

You are indeed a tower of intellect. I bet you got all kinds of net.groupies.

>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).

Of course! Ah-ha! It's so obvious. If you say it's true, it must be.

You don't happen to have a proof, do you?

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

Oh, Dan, I am the dust beneath your feet. I grovel for enlightment. Please
answer the query, which is too much for my feeble brain.

I'm running my program on a machine #1, maxing out its memory. You run your
analyzer on a slightly larger machine #2. Well, I'm maxed and need an
upgrade--I use machine #2. I guess you need a slight larger machine #3.
Oh, but I'll that one instead. Now you need a slightly larger machine #4.

Silly me, but it seems that I can consume machines faster than you can produce
them. If, as you claim, resources are inherently limited, it seems I'll
be using some machine #n and there won't be a machine #n+1 for your analyzer.
Is my program still a self-contained C program? If so, how are you going to
run your analyzer?
-- 
|-In compliance with DoC,---------------------Steven Ryan----------------------|
| this posting is devoid         |            2400 Geng Road, Palo Alto, CA    |
| of all information.            |            smryan@wyrmham.clipper.ingr.com  |
|-And Oliver North married William Secord/and gave birth to a little Teheran.--|