Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!samsung!crackers!m2c!risky.ecs.umass.edu!dime!chelm.cs.umass.edu!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <30505@dime.cs.umass.edu>
Date: 14 May 91 14:17:30 GMT
References: <1991May10.155454.2239@maths.nott.ac.uk> <3125@cirrusl.UUCP> <3069@optima.cs.arizona.edu>
Sender: news@dime.cs.umass.edu
Organization: University of Massachusetts, Amherst
Lines: 19

In article <3069@optima.cs.arizona.edu> kwalker@cs.arizona.edu (Kenneth Walker) writes:
>
>For the moment, lets assume our analysis routine manages to place a bound
>on the number of states (size of memory) that will exist in the compiled
>program and that the analysis program must itself execute within the same
>finite-state machine. Because the analysis routine must itself be coded
>in some of the states, it does not have enough states to represent the
>states of the program it is analysing. Is there any hope (in a theoretical
>sense) of a finite state machine computing interesting properties of
>an arbitrary finite state machine of its own size?
>


No. But, a finite machine of size X can solve the halting problem for
finite machines of size Y, supposing that Y is sufficiently smaller than X.
In practical terms, this means a cross-compiler on a CRAY might be able
to detect failure to halt in programs being compiled for a small micro.
But, the exact ratio between X and Y depends on your ingenuity,the
programming language, and  the class of programs you find interesting.