Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!ncar!noao!arizona!kwalker
From: kwalker@cs.arizona.edu (Kenneth Walker)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Summary: finite analysis
Message-ID: <3069@optima.cs.arizona.edu>
Date: 10 May 91 22:56:01 GMT
References: <2990@optima.cs.arizona.edu> <1991May10.155454.2239@maths.nott.ac.uk> <3125@cirrusl.UUCP>
Sender: news@cs.arizona.edu
Lines: 12


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?

  Ken Walker / Computer Science Dept / Univ of Arizona / Tucson, AZ 85721
  +1 602 621-4252  kwalker@cs.arizona.edu {uunet|allegra|noao}!arizona!kwalker