Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!cs.umu.se!christer
From: christer@cs.umu.se (Christer Ericson)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <1990Nov14.150535.25991@cs.umu.se>
Date: 14 Nov 90 15:05:35 GMT
References: <23904:Nov905:22:5290@kramden.acf.nyu.edu> <11839@life.ai.mit.edu> <3975:Nov1323:25:4390@kramden.acf.nyu.edu>
Sender: news@cs.umu.se (News Administrator)
Organization: Dep. of Info.Proc, Umea Univ., Sweden
Lines: 33

In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>Here are two articles about the practical solution to the halting
>problem. The first, from February this year, is short and should give
>people an idea of the resources implied by ``practical solution.''
>(Practical enough that it could reasonably be an option in Saber-C.)
>
> [lots of stuff deleted]
>
>The halting problem is to determine whether a given program loops forever.
>This is an uncomputable function of a program, as we all know.
>
>But if a program is restricted to a finite number of states then the
>problem is computable. The practical solution is that we run the program
>on two machines with that number of states, one machine exactly twice as
>fast as the other; if the program loops in time t to t+u, then we will
>see the machines in exactly the same state at time 3t to 3t+3u.
>
> [even more deleted stuff]

You think this is new? 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*. Practically, given the size of available
memory on todays machines, for most problems I'd say it's not. Also, the metod
you described is nothing new, it's a commonly used metod to find cycles in
iterative procedures (hey, A. K. Dewdney has described it in his column in
Scientific American, so everyone - give or take a few - should be familiar
with it :-).  Solving the halting problem for a Turing machine (or any other
machine with unlimited memory) is something entirely different.


| Christer Ericson            Internet: christer@cs.umu.se [130.239.1.101] |
| Department of Computer Science, University of Umea, S-90187 UMEA, Sweden |