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

[Peter Desnoyers]

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 (david wald) writes:
>
>> [halting problem for C programs, for FSMs/TMs, etc.]
>
>I think that theoretically (this is COMP.THEORY, isn't it?) the two questions
>are the same. 

no, no, no. C as specified in the standard is Turing-equivalent - you
can't assume any bound on the amount of memory that can be allocated. 

A particular machine running C is a limited-tape Turing machine, which
is equivalent to an FSM.  

Food for thought - does this piece of C code halt in general? on a
specific machine? Why?

    for (i = 0;; i++)
      if (!malloc(1))	/* "move tape head right" */
        break;		/* until we run out of memory */
    if (i & 1)		/* if i is odd */
      for (;;);		/* loop */
    exit();		/* else halt */

This should underscore the difference between C being a TM and a
practical computer running C being an FSM, and why the second result
is so completely useless.

				Peter Desnoyers