Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!caen!uflorida!haven!adm!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <8839:Nov2100:33:3990@kramden.acf.nyu.edu>
Date: 21 Nov 90 00:33:39 GMT
References: <13530:Nov1419:56:3790@kramden.acf.nyu.edu> <156@garth.UUCP> <1990Nov20.213454.10879@craycos.com>
Organization: IR
Lines: 32

Skip if you saw James' error.

In article <1990Nov20.213454.10879@craycos.com> jrbd@craycos.com (James Davies) writes:
> >>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.
> main(argc,argv) {
> 	int I_halt();
> 	if (I_halt(argv[0])) {
> 		while(1);
> 	} else {
> 		exit(0);
> 	}
> }
> Please write I_halt.  It should return 1 if its argument program
> halts, 0 if it doesn't. 

We are all aware that it is impossible for a fixed algorithm *within*
machine M to solve the halting problem for machine M (provided that M is
not utterly trivial). But the solution takes advantage of a new machine
*outside* M. Your artificially restricted question has nothing to do
with the problem at hand.

> Feel free to consult books or notes,
> other programmers, Nobel prize winners, etc.

Your sarcasm would be more appropriate if you had shown that you
understood anything written in previous articles in this thread.

---Dan