The Halting Problem (was: YALF (yet another lint foulup))

[david wald]

In article <47372 at yale-celray.yale.UUCP> Krulwich-Bruce at cs.yale.edu
(Bruce Krulwich) writes:
>In article <47306 at yale-celray.yale.UUCP>, wald-david at cs.yale.edu (david
wald) writes:
>>In article <2686 at ficc.uu.net> jair at ficc.uu.net (jair bobys) writes:
>>>FSAs, or Finite State Automata, model Regular Languages.  Since the Regular
>>>Languages are a subset of the Recursively Enumerable Languages, as are all
>>>other types (Context Free and Context Sensitive), and the Turing Machine
>>>models Recursively Enumerable Languages, the FSAs are, loosely speaking, a
>>>subset of Turing Machines (as concerns computing power).  As a result of
>>>this, if something is provably uncomputable by a Turing Machine, as in the
>>>case of the Halting Problem, it is simply uncomputable by any machine.
>>
>>But the question was not whether a FSA could check the halting problem.
>>Rather, it was (originally) whether it is possible to check for
>>termination of C programs, and (by the third posting) whether the
>>halting problem for FSAs is computable (by a TM, presumably, although
>>perhaps by an FSA).  It has already been pointed out that 1) the answer
>>to the second question is "yes", and 2) that the two questions are not
>>equivalent.
>
>I think that theoretically (this is COMP.THEORY, isn't it?) the two questions
>are the same.  On any particular machine that you run a C program there is a
>finite amount of memory/storage.  This is the same as a bounded-TM, in which
>the TM program is different from the bound placed on the space it can use.

I don't think they are.  This discussion began with the question of
whether it is possible to determine from a C program whether it will
halt.  Given that the program itself gives you no information about
the size of the system it will be running on, you cannot take that
bound into account.  Therefore, the only meaningful deterministic
interpretation of the question "does the program halt" is "does the
program halt, assuming its malloc()s never fail for lack of memory."
To do the analysis properly, I suppose you should treat the program as
a description of a nondeterministic machine, on which each malloc()
will either fail or succeed, but the point about the upper bound still
holds.

Either way, then, you cannot place a bound on the machine, so the
halting problem for C programs remains undecidable.

Taking the program together with a machine, the problem can be treated
as a FSA, in which case halting is certainly decidable, if
unreasonable.

On the other hand, the comment I was responding to stated that the
halting problem was undecidable *by* an FSA, which is true, but a
different question.



============================================================================
David Wald                                              wald-david at yale.UUCP
waldave at yalevm.bitnet                                 wald-david at cs.yale.edu
"A monk, a clone and a ferengi decide to go bowling together..."
============================================================================