wald-david@CS.YALE.EDU (david wald) (01/13/89)
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.yale.edu (david wald) writes: >>In article <2686@ficc.uu.net> jair@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@yale.UUCP waldave@yalevm.bitnet wald-david@cs.yale.edu "A monk, a clone and a ferengi decide to go bowling together..." ============================================================================
mat@mole-end.UUCP (Mark A Terribile) (01/13/89)
> | ... Never returning is a hard property to check in C. > |Try "uncomputable." > > But is this equivalent to the halting problem? ... Real computers are > finite state machines ... Does the halting problem hold for FSAs? Consider a machine with 64K of 8-bit memory. (By today's standards, that's hardly large enough for a ``hello, world'', especially if you are using a window package.) You have 2 ** 16 words of memory or 2 ** 19 bits. The number of states that your machine can reach is 2 ** ( 2 ** 19 ) or about 2 ** 5E5 or about 10 ** 2E5 (within 40%). A machine with a cycle time of 1 attosecond could, in the limit, mimimally visit all those states in only 10 000 or so seconds. But that's not enough, because you have to examine all possible sequences through all of those states. Now you are talking about ( 10 ** 2E5 )! , which is getting rather large. Now make that a 1 Meg machine. You have now got 2 ** 23 bits, or about 2 ** ( 10 ** 7 ) states ... For all practical purposes, the problem of exhaustively verifying all sequences through such state sets for whatever input is uncomputable. -- (This man's opinions are his own.) From mole-end Mark Terribile
nick@ccicpg.UUCP (Nick Crossley) (01/14/89)
In article <47406@yale-celray.yale.UUCP> wald-david@CS.YALE.EDU (david wald) writes: >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." >... >Either way, then, you cannot place a bound on the machine, so the >halting problem for C programs remains undecidable. >... Now, it is a long time since I was taught this stuff, but I seem to recall one point which has not yet been brought up. The 'Halting Problem' is that it is not possible to build a Turing machine which will read the description of *any arbitrary* Turing machine and *any arbitrary* input, and decide whether or not that Turing machine will halt given that input. It is not necessarily impossible to decide whether or not a particular Turing machine/program will halt. Indeed, in many cases it is trivial to show that they do, given any input: int main (void) /* or (int argc, char *argv[]) whichever you like */ { return 0; } Further, the problem in the general case is not that you might get the wrong answer, it is just that your super checking program itself might not halt for some program/input pairs. -- <<< standard disclaimers >>> Nick Crossley, CCI, 9801 Muirlands, Irvine, CA 92718-2521, USA. (714) 458-7282 uunet!ccicpg!nick / nick@ccicpg.UUCP
desnoyer@Apple.COM (Peter Desnoyers) (01/14/89)
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