David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 39 (3):489-495 (1974)
In this paper we investigate some families of decision problems associated with a restricted class of Post canonical forms, specifically, those defined over one-letter alphabets whose productions have single premises and contain only one variable. For brevity sake, we call any such form an RPCF (Restricted Post Canonical Form). Constructive proofs are given which show, for any prescribed nonrecursive r.e. many-one degree of unsolvability D, the existence of an RPCF whose word problem is of degree D and an RPCF with axiom whose decision problem is also of degree D. Finally, we show that both of these results are best possible in that they do not hold for one-one degrees
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Charles E. Hughes (1975). Sets Derived by Deterministic Systems with Axiom. Mathematical Logic Quarterly 21 (1):71-80.
Similar books and articles
M. Gehrke & H. A. Priestley (2007). Duality for Double Quasioperator Algebras Via Their Canonical Extensions. Studia Logica 86 (1):31 - 68.
Timothy J. Surendonk (2001). Canonicity for Intensional Logics with Even Axioms. Journal of Symbolic Logic 66 (3):1141-1156.
Charles E. Hughes & David W. Straight (1980). Word Problems for Bidirectional, Single-Premise Post Systems. Notre Dame Journal of Formal Logic 21 (3):501-508.
Nguyen Cat Ho & Helena Rasiowa (1987). Semi-Post Algebras. Studia Logica 46 (2):149 - 160.
Maria Lasonen-Aarnio (2008). Single Premise Deduction and Risk. Philosophical Studies 141 (2):157 - 173.
Charles E. Hughes (1976). Two Variable Implicational Calculi of Prescribed Many-One Degrees of Unsolvability. Journal of Symbolic Logic 41 (1):39-44.
Christopher Steinsvold (2010). A Canonical Topological Model for Extensions of K. Studia Logica 94 (3):433 - 441.
Added to index2009-01-28
Total downloads5 ( #242,089 of 1,140,344 )
Recent downloads (6 months)1 ( #140,127 of 1,140,344 )
How can I increase my downloads?