Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!tut.cis.ohio-state.edu!bloom-beacon!apple!desnoyer
From: desnoyer@Apple.COM (Peter Desnoyers)
Newsgroups: comp.lang.c
Subject: Re: The Halting Problem (was: YALF (yet another lint foulup))
Message-ID: <23913@apple.Apple.COM>
Date: 13 Jan 89 18:43:01 GMT
References: <9255@smoke.BRL.MIL> <379@lakart.UUCP> <9341@ihlpb.ATT.COM> <9371@ihlpb.ATT.COM> <2686@ficc.uu.net> <47306@yale-celray.yale.UUCP> <47372@yale-celray.yale.UUCP>
Organization: Apple Computer Inc, Cupertino, CA
Lines: 29

In article <47372@yale-celray.yale.UUCP> Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) writes:
>In article <47306@yale-celray.yale.UUCP>, wald-david@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