Article View: comp.lang.misc
Article #3810Re: The Halting Problem is _not_ solvable on real com
From: Kenneth Walker
Date: Fri, 10 May 1991 22:56
Date: Fri, 10 May 1991 22:56
12 lines
1230 bytes
1230 bytes
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
Technical Details
Message-ID:
<3069@optima.cs.arizona.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!ncar!noao!arizona!kwalkerReferences:
<2990@optima.cs.arizona.edu> <1991May10.155454.2239@maths.nott.ac.uk> <3125@cirrusl.UUCP>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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