[FOM] Arithmetic-free theory of formal systems?
Dennis E. Hamilton
dennis.hamilton at acm.org
Mon May 17 19:26:50 EDT 2004
In <http://www.cs.nyu.edu/pipermail/fom/2004-May/008206.html>
Tim Chow asks "... Is there a way of developing a
theory of formal systems without any reference to arithmetic?"
Take a look at Raymond Smullyan's "Theory of Formal Systems." It is one of
the Princeton Annals publications (No. 47, 1961), and I see that it is still
in print, <http://pup.princeton.edu/titles/2398.html>.
There is also a (JSL?) piece from it on Elementary Formal Systems.
He uses
E11
and Ex -> Ex11
as an example of you-know what. I don't have a copy any longer so I can't
tell you if he comes closer to what you are talking about. He does get to
undecidability and I don't recall how he does the "arithmetization" of the
formal system.
I like the above example (and your two) because, in formal terms, they are
each, taken separately, indistinguishable from this one:
N0
Nx -> Nx'
Now, looking at Tim's questions, how is it we are willing to believe that,
taking the scheme as a generation rule, duplicates are never produced and
there is no end to the sequences that satisfy N? Have I presumed numbers?
Where?
PS: Amazon.com even has a listing for the book, and there was this wonderful
example of natural language processing when I looked: "Customers interested
in Theory of Formal Systems (AM-47) may also be interested in: Dresses at
Macy's ... ."
- orcmid
-------------------------------
Dennis E. Hamilton | KIT eLearning student | University of Liverpool on-line
M.Sc in IT
mailto:Dennis.Hamilton at Liverpool.ac.uk | gsm:+1-206.779.9430
http://orcmid.com | http://nfoWare.com | http://Miser-theory.info
OpenPGP public key fingerprint BFE5 EFB8 CB51 8781 5274 C056 D80D 0C3F A393
27EC
More information about the FOM
mailing list