Equational derivation vs. computation

&
Annals of Pure and Applied Logic 70 (1):17-49 (1994)
  Copy   BIBTEX

Abstract

Subrecursive hierarchy classifications are used to compare the complexities of recursive functions according to their derivations in a version of Kleene's equation calculus, and their computations by term-rewriting. In each case ordinal bounds are assigned, and it turns out that the respective complexity measures are given by a version of the Fast Growing Hierarchy, and the Slow Growing Hierarchy. Known comparisons between the two hierarchies then provide ordinal trade-offs between derivation and computation. Characteristics of some well-known subrecursive classes are also read off

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)90068-x

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,752

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Equational approach to argumentation networks.D. M. Gabbay - 2012 - Argument and Computation 3 (2-3):87 - 142.
Theories with equational forking.Markus Junker & Ingo Kraus - 2002 - Journal of Symbolic Logic 67 (1):326-340.
A note on definability in equational logic.George Weaver - 1994 - History and Philosophy of Logic 15 (2):189-199.
Conceptual and Derivation Systems.Jiří Raclavský & Petr Kuchyňka - 2011 - Logic and Logical Philosophy 20 (1-2):159-174.
Explaining computation without semantics: Keeping it simple.Nir Fresco - 2010 - Minds and Machines 20 (2):165-181.
Decidability of the Equational Theory of the Continuous Geometry CG(\Bbb {F}).John Harding - 2013 - Journal of Philosophical Logic 42 (3):461-465.
Proving consistency of equational theories in bounded arithmetic.Arnold Beckmann† - 2002 - Journal of Symbolic Logic 67 (1):279-296.
Searle’s Derivation, Natural Law, and Moral Relativism.Edmund Wall - 2008 - Philosophia 36 (2):237-249.
Near-equational and equational systems of logic for partial functions. I.William Craig - 1989 - Journal of Symbolic Logic 54 (3):795-827.
Near-equational and equational systems of logic for partial functions. II.William Craig - 1989 - Journal of Symbolic Logic 54 (4):1181-1215.
Review: A. Tarski, H. Arnold Schmidt, K. Schutte, H.-J. Thiele, Equational Logic and Equational Theories of Algebras. [REVIEW]Ralph Seifert - 1971 - Journal of Symbolic Logic 36 (1):161-162.
Cognition is not computation: The argument from irreversibility.Selmer Bringsjord - 1997 - Synthese 113 (2):285-320.
Equational Reasoning in Non-Classical Logics.Marcelo Frias & Ewa Orlowska - 1998 - Journal of Applied Non-Classical Logics 8 (1-2):27-66.
On the equational theory of projection lattices of finite von Neumann factors.Christian Herrmann - 2010 - Journal of Symbolic Logic 75 (3):1102-1110.

Analytics

Added to PP
2014-01-16

Downloads
29 (#548,607)

6 months
4 (#778,909)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Term rewriting theory for the primitive recursive functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.

Add more citations

References found in this work

[product]¹2-logic, Part 1: Dilators.Jean-Yves Girard - 1981 - Annals of Mathematical Logic 21 (2):75.
Π12-logic, Part 1: Dilators.Jean-Yves Girard - 1981 - Annals of Mathematical Logic 21 (2-3):75-219.
Some Classes of Recursive Functions.Andrzej Grzegorczyk - 1955 - Journal of Symbolic Logic 20 (1):71-72.
The slow-growing and the grzecorczyk hierarchies.E. A. Cichon & S. S. Wainer - 1983 - Journal of Symbolic Logic 48 (2):399-408.

View all 8 references / Add more references