Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!udel!ee.udel.edu
From: new@ee.udel.edu (Darren New)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <36480@nigel.ee.udel.edu>
Date: 15 Nov 90 21:23:07 GMT
References: <13350:Nov1419:44:2790@kramden.acf.nyu.edu> <GESSEL.90Nov14165831@carthage.cs.swarthmore.edu> <5785:Nov1519:19:5390@kramden.acf.nyu.edu>
Sender: usenet@ee.udel.edu
Organization: University of Delaware
Lines: 33
Nntp-Posting-Host: estelle.ee.udel.edu

In article <5785:Nov1519:19:5390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>See, this is what I mean about computer scientists. The computational
>model I work with is realistic---it's just my mental picture of what can
>be coded on lots of real machines. As I said before, it's finite. It has
>very, very little to do with a Turing machine.

But the program you write to do the testing you describe requires some memory.
Hence, because of your finite machine, there are some problems which the 
program under test cannot solve which it would have been able to solve had
you given it that extra memory. If it cannot solve the problem (i.e., if it
gives a different answer) then it might go into a loop.  For example, let's
try this pseudoprogram:

const x = any integer;
begin
  for i := 0 to x do begin
    y = malloc(1);
    if (y == NULL) begin
	while (1) ;
	end
    end
end.

For any given size machine, there will be a value for X where the program
will not halt when you test it but will halt if you run it alone.  An "almost
right" solution to the halting problem may be useful, but I wouldn't call it
"a practical solution to the halting problem".      -- Darren
    
-- 
--- Darren New --- Grad Student --- CIS --- Univ. of Delaware ---
----- Network Protocols, Graphics, Programming Languages, 
      Formal Description Techniques (esp. Estelle), Coffee, Amigas -----
              =+=+=+ Let GROPE be an N-tuple where ... +=+=+=