Re: [CL] Re: Decidability
A few 'reflections' re: "Decidability (or not) of an algorithm is a *simple*
mathematical fact".
Compare, e.g., Halmos, "The Basic Concepts of Algebraic Logic", Amer. Math.
Monthly, vol. 53 (1956) [Introduction to _Algebraic Logic_, Halmos].
P. 33: "... What has been said so far makes the Godel incompleteness theorem
take the following form: not every Peano algebra is syntactically complete.
In view of the algebraic characterization of syntactic completeness this can
be rephrased thus: not every Peano algebra is a simple polyadic algebra.
This is the description that was promised above. What follows is another
rephrasing of this description: the rephrasing, possibly of some mnemonic
value, makes its point by making a pun. Consider one of the systems of
axiomatic set theory that is commonly accepted as a foundation for all
extant mathematics. There is no difficulty in constructing polyadic algebras
with sufficiently rich structure to mirror that axiomatic system in all
detail. Since set theory is, in particular, an adequate foundation for
elementary arithmetic, each such algebra is a Peano algebra. The elements of
such a Peano algebra correspond in a natural way to the propositions
considered in mathematics; it is stretching a point, but not very far, to
identify such an algebra with mathematics itself. Some of these
'mathematics' may turn out to possess no non-trivial proper ideals, i.e., to
be syntactically complete; the Godel theorem implies that some of them will
certainly be syntactically incomplete. The conclusion is that the crowning
glory of modern logic (algebraic or not) is the assertion: *mathematics is
not necessarily simple*."
Also Wikipedia, The Halting Problem:
http://en.wikipedia.org/wiki/Halting_problem
Note in particular the remark there: " There is another caveat. The
undecidability of the halting problem relies on the fact that algorithms are
assumed to have potentially infinite storage: at any one time they can only
store finitely many things, but they can always store more and they never
run out of memory. If the memory and external storage of a machine is
limited, as it is for any computer which actually exists, then the halting
problem for programs running on that machine can be solved with a general
algorithm (albeit an extremely inefficient one). "
Finally, an interesting overview paper: "Logic for Computer Science: The
Engineering Challenge"
http://www-i7.informatik.rwth-aachen.de/%7Ethomas/papers/dagstuhl2.ps.gz
Pg. 9 --
"...The systems of computer science cover such a wide range of levels of
hierarchy today that it even seems doubtful to try to cover them by just one
methodology. In natural science, it is agreed that different levels of
organization require different concepts and laws, as seen in the division of
science into fields like physics, chemistry, and biology. The hierarchical
world of information processing systems has reached a richness where the
same question arises. An example may illustrate this aspect: It is clear
that in the memory cells of a processor a single bit matters. But on the
level of the world-wide web this is no more true; there, it usually does not
even matter whether a whole server is down. So, in teaching "foundations of
computer science", it is probably no more appropriate to map everything (in
principle) to the world of finite automata or Turing machines. This is like
trying to explain chemical or biological phenomena just with the concepts
and laws of physics.
4.5 The challenge of the web
In the past ten years, the development of the world-wide web has caused a
revolution in the world of information processing. The framework for the
publication and exchange of scientific results is changing deeply and
rapidly. Today, a large part of scientific knowledge is available not only
in symbolic form (i.e., in texts), but also in a format which supports
machine-based search, analysis, and composition. This gives a completely new
perspective to Leibniz's project of a universal framework for the management
of knowledge. It is rather clear that new kinds of "inference" and
"composition of propositions" have to be developed to handle the potentials
of the web adequately. Leibniz would probably be enthusiastic about this
wonderful new arena for logic. But in academic logic, these practical
Leibnizian tasks do not attract much interest. Instead, computer scientists,
in particular data base researchers, are addressing these questions.
Sometimes I have the impression that we are living in a golden age of logic
but that logic does not know it..."
Moral: life is difficult, but not impossible. QED :)
Cheers,
Jay
----- Original Message -----
From: "Chris Menzel" <cmenzel@tamu.edu>
To: "Michael Gruninger" <gruning@cme.nist.gov>
Cc: <standard-upper-ontology@listserv.ieee.org>; <cg@cs.uah.edu>;
<cl@philebus.tamu.edu>; "Norbert E.Fuchs" <fuchs@ifi.unizh.ch>;
<heflin@cse.lehigh.edu>
Sent: Wednesday, August 25, 2004 05:46
Subject: Re: [CL] Re: Decidability
> On Thu, Aug 05, 2004 at 11:43:27AM -0400, Michael Gruninger wrote:
> > Christopher Welty wrote:
> >
> > John,
> >
> > Decidability (or not) of an algorithm is a simple mathematic fact.
> > There is no more or less to it than that. It is as important a
> > property to know about a reasoner (that it is undecidable or
decidable)
> > as it is to know that I have a sort algorithm that's nlogn or n^2.
You
> > seem to be treating decidability and complexity class as somehow
> > different (ie one is important and one is not).
> >
> > -Chris
> >
> > Hi Chris,
> >
> > it seems a little strange to refer to decidability as a property of
an
> > algorithm.
>
> Indeed -- for a problem (or function, or whatever) to be decidable is
> (assuming Church's Thesis) exactly to *have* an algorithm that does the
> deciding. (I'm also sure that Chris W was just speaking hastily above
> and is quite well aware of this.)
>
> Sorry to be weighing in so late here; I've been out of touch most of
> August...
>
> -chris
> _______________________________________________
> CL mailing list
> CL@philebus.tamu.edu
> http://philebus.tamu.edu/mailman/listinfo/cl