Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!samsung!crackers!m2c!risky.ecs.umass.edu!dime!chelm.cs.umass.edu!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <31195@dime.cs.umass.edu>
Date: 29 May 91 04:04:57 GMT
References: <31051@dime.cs.umass.edu> <k3ZN38w164w@mantis.co.uk>
Sender: news@dime.cs.umass.edu
Organization: University of Massachusetts, Amherst
Lines: 59

In article <k3ZN38w164w@mantis.co.uk> mathew@mantis.co.uk (CNEWS MUST DIE!) writes:
>Basically, for any moderately complicated ANSI C program the dimensions of
>the input domain and the range of each dimension will be so large that trying
>all combinations will be infeasible on even the largest computers. I'll leave
>it to someone else to do some sums to demonstrate this.
>
>In short, determining the halting status of ANSI C programs is not feasible
>for real programs; and it's not possible for general ANSI C programs, because
>general ANSI C programs might have arbitrarily large input spaces making
>analysis require impossible amounts of memory and CPU time.

This discussion has passed into a terminally dull zone. So, I'm going
to give up, with some final words. First, I'd like to return to my
orignal point: computer scientists overuse and misuse the notion
of undecidable problems and in doing so may be shutting off some interesting
research avenues. It is not clear that there are any interesting problems
in compiler design and program verification which are undecidable. This
is simply because we are seldom interested in knowing whether computations
can be done in unbounded time and space, rather we generally want to know
if a problem can be solved using  some bounded level of resources, e.g.,
within 10 nanoseconds, within polynomial/exponential time,
within n time units where n is a parameter, within 100 million steps
times the size of the input, using no more than MAXPROC
space etc. etc.   Second, I want to reiterate that it is important to
precisely distinguish between "hard" and "impossible". There are some
problems that we know are impossible to solve algorithmically, and there
are other problems which seem intractable. But, just because the
readers of this newsgroup are incapable of thinking up an algorithm
or theoretical result on the fly, does not imply that there is no
such algorithm, or no result that will melt  a currently intractable
problem. Finally, a quote:
 
\begin{quote}
Turing machines are widely considered to be the abstract prototype of
digital computers; workers in the field, however, have felt more and
more that the notion of a Turing machine is too general to serve as
an accurate model of actual computers. It is well known that for even
a simple calculation it is impossible to give an {\it a priori} upper
bound on the amount of tape a Turing machine will neeed for any given
computation. It is precisely this feature which renders Turing's
concept unrealistic. 
In the last few years the idea of a {\em finite automata} has appeared
in the literature. These are machines having only a finite number
of internal states that can be used for memory and computation. The
restriction of finiteness appears to give a better approximation to
the idea of a physical machine. Of course, such machines cannot do as
much as Turing machines, but the advantage of being able to compute a
general recursive function is questionable, since very few of these
functions come up in practical applications."
\end{quote}

author="Rabin M.O.  and  Dana Scott",
title="Finite automata and their decision problems",
journal="IBM Journal of Research and Development",
vol={3},
number={2},
month={April},
year={1959},
page={114-125}