Article View: comp.lang.functional
Article #316Re: Primitive Recursive Arithmetic
From: Chet Murthy
Date: Fri, 15 Jun 1990 16:13
Date: Fri, 15 Jun 1990 16:13
19 lines
1328 bytes
1328 bytes
jrk@sys.uea.ac.uk (Richard Kennaway) writes: >Technical question: are there functions which are expressible in PRA >but much more compactly expressible in (e.g.) Horn clauses (or some other >programming language more powerful than PRA)? Are there any practically >useful such functions? I would be quite certain of this one. The work of Friedman on long proofs of small theorems is relevant here, I think. There are almost certainly practical uses for such functions - all of Ramsey theory was not developed for mathematician's sexual sublimation. Neither was the theory of well-quasi-orders. Both of these areas are applicable to term-rewriting, etc, and both of these areas are rife with recursive functions with ordinal running times above epsilon_0. --chet-- murthy@cs.cornell.edu
Technical Details
Message-ID:
<42269@cornell.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!attcan!uunet!mailrus!cornell!murthyReferences:
<15421@dime.cs.umass.edu> <GUTTMAN.90Jun12105623@darjeeling.mitre.org> <15548@dime.cs.umass.edu> <3594@rex.cs.tulane.edu> <15591@dime.cs.umass.edu> <1566@sys.uea.ac.uk>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!attcan!uunet!mailrus!cornell!murthy From: murthy@algron.cs.cornell.edu (Chet Murthy) Newsgroups: comp.lang.functional Subject: Re: Primitive Recursive Arithmetic Message-ID: <42269@cornell.UUCP> Date: 15 Jun 90 16:13:58 GMT References: <15421@dime.cs.umass.edu> <GUTTMAN.90Jun12105623@darjeeling.mitre.org> <15548@dime.cs.umass.edu> <3594@rex.cs.tulane.edu> <15591@dime.cs.umass.edu> <1566@sys.uea.ac.uk> Sender: nobody@cornell.UUCP Organization: Cornell Univ. CS Dept. Ithaca NY Lines: 19