Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!julius.cs.uiuc.edu!apple!bionet!synoptics!unix!garth!smryan
From: smryan@garth.UUCP (Steven Ryan)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <156@garth.UUCP>
Date: 19 Nov 90 19:52:15 GMT
References: <11839@life.ai.mit.edu> <3975:Nov1323:25:4390@kramden.acf.nyu.edu> <1990Nov14.150535.25991@cs.umu.se> <13530:Nov1419:56:3790@kramden.acf.nyu.edu>
Reply-To: smryan@garth.UUCP (Steven Ryan)
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 18

>> If a program, or rather a computer, is restricted to
>> a finite number of states (which all modern computers are) then it's nothing
>> more than a finite automaton and therefore the halting problem for these
>> machines is solvable *in theory*.
>
>Right. It's also solvable in practice.

I assume this includes checking each reel of tape in the library that the
program has accessed, each reel of tape that the program accessed but have
been moved off site because the tape library is full, and eventually every
reel of tape which was moved off planet because the planet is full.

Can you really put an a priori bound on the length of the tape? I suppose
we could put bounds based on the number of atoms in the universe, IF you
can deduce the number of atoms. (Deduce is not the same thing physics does.)
-- 
...!uunet!ingr!apd!smryan                                       Steven Ryan
...!{apple|pyramid}!garth!smryan              2400 Geng Road, Palo Alto, CA