Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <3430@optima.cs.arizona.edu>
Date: 22 May 91 04:53:07 GMT
Sender: news@cs.arizona.edu
Lines: 27

In article  <30835@dime.cs.umass.edu> victor yodaiken writes:
]In article <3410@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
]>In article  <30814@dime.cs.umass.edu> victor yodaiken writes:
]>]... I argue that it is possible, in theory, for a C
]>]compiler to detect all paths that lead to non-terminating loops and to
]>]flag these paths.
]>I argue that this is impossible in theory.
]Your argument is that the task is difficult...
].. Impractical != impossible. You must understand "in theory" in a
]nonstandard way.

No, it's just that you seem to be trying to be trying to have it both
ways: "Since a computer has a finite number of states, it is possible
in principle to solve the halting problem for it, since you can always
just traverse all possible states."  The first part of the sentence
implies that you are modeling a computer as an FSM.  The second part
of the sentence implies that you are modeling a computer as a
non-finite state machine, since you are assuming that you can traverse
all possible states.

Pick your model.  No matter which one you pick, you cannot solve the
halting problem for all programs on a given machine with a program on
that machine.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman