Recursive Predicates and Quantifiers

DOI10.2307/1990131zbMath0063.03259OpenAlexW4236482601WikidataQ55877787 ScholiaQ55877787MaRDI QIDQ5843994

Stephen C. Kleene

Publication date: 1943

Full work available at URL: https://doi.org/10.2307/1990131

Related Items (71)

Propositional Calculus and Realizability ⋮ Classes of Recursively Enumerable Sets and Their Decision Problems ⋮ Recursive Functions and Intuitionistic Number Theory ⋮ Productive Sets ⋮ Leon Henkin the Reviewer ⋮ Effective topological spaces. III: Forcing and definability ⋮ Approximating approximate reasoning: fuzzy sets and the Ershov hierarchy ⋮ Parametric Church's thesis: synthetic computability without choice ⋮ The metamathematics of Stable Ramsey’s Theorem for Pairs ⋮ Index sets and presentations of complexity classes ⋮ Bemerkung über die Primpolynomzerlegung in endlich vielen Schritten ⋮ Zur Theorie der konstruktiven Wohlordnungen ⋮ Simplicity, immunity, relativizations and nondeterminism ⋮ Index sets related to prompt simplicity ⋮ Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic ⋮ The incompleteness theorems after 70 years ⋮ Darstellungen der (im KALMÁR-CSILLAG'schen Sinne) Elementaren Funktionen ⋮ Formalism and intuition in computability ⋮ On the Hardness of Almost–Sure Termination ⋮ An effectively closed set with no join property* ⋮ Specification and verification of concurrent systems by causality and realizability ⋮ Hierarchies of number-theoretic predicates ⋮ The never-ending recursion ⋮ Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability ⋮ Levels of undecidability in rewriting ⋮ Intermediate logics and the de Jongh property ⋮ Computation as an unbounded process ⋮ Classes of Polish spaces under effective Borel isomorphism ⋮ INCOMPLETENESS VIA PARADOX AND COMPLETENESS ⋮ Can Church's thesis be viewed as a Carnapian explication? ⋮ Unnamed Item ⋮ All Quantifiers Versus the Quantifier All ⋮ Recursion-theoretic ranking and compression ⋮ On predicates expressible in the $1$-function quantifier forms in Kleene Hierarchy with free variables of type $2$ ⋮ Toward a theory of intelligence ⋮ On the hardness of analyzing probabilistic programs ⋮ Characterizing parallel hierarchies by reducibilities ⋮ Conceptual Confluence in 1936: Post and Turing ⋮ Theses for Computation and Recursion on Concrete and Abstract Structures ⋮ Why Turing’s Thesis Is Not a Thesis ⋮ My Life as a Logician ⋮ Hyperarithmetical Sets ⋮ A second step toward the strong polynomial-time hierarchy ⋮ Using computability to measure complexity of algebraic structures and classes of structures ⋮ Gödel's reception of Turing's model of computability: the shift of perception in 1934 ⋮ Levy and set theory ⋮ The many forms of hypercomputation ⋮ On the degree spectrum of a $\Pi ^0_1$ class ⋮ The Church-Turing Thesis over Arbitrary Domains ⋮ A second step toward the polynomial hierarchy ⋮ Automata theory and control theory - a rapprochement ⋮ Exotic quantifiers, complexity classes, and complete problems ⋮ Definability, decidability, complexity ⋮ On simplicity of formulas ⋮ Arithmetical Predicates and Function Quantifiers ⋮ Kleene’s Amazing Second Recursion Theorem ⋮ Computable permutations and word problems ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ The use of lists in the study of undecidable problems in automata theory ⋮ Computing degrees of unsolvability ⋮ Recursive and Recursively Enumerable Orders ⋮ On the realizations of predicate formulas ⋮ An enumeration of the primitive recursive functions without repetition ⋮ A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY ⋮ Effective topological spaces. I: A definability theory ⋮ The theory of recursive functions, approaching its centennial ⋮ Recursive Functions and Intuitionistic Number Theory ⋮ The minimum degree of recursively representable choice functions ⋮ Effective topological spaces. II: A hierarchy ⋮ Péter on Church's thesis, constructivity and computers ⋮ Existential Definability in Arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The inconsistency of certain formal logics
• General recursive functions of natural numbers
• A Theory of Positive Integers in Formal Logic. Part I
• An Unsolvable Problem of Elementary Number Theory
• Some Properties of Conversion
• A note on recursive functions
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Gödel Theorems for Non-Constructive Logics
• The constructive second number class
• On notation for ordinal numbers
• Systems of Logic Based on Ordinals^†
• On undecidable statements in enlarged systems of logic and the concept of truth
• Some aspects of the problem of mathematical rigor
• The inconsistency of certain formal logics
• On the Forms of the Predicates in the Theory of Constructive Ordinals

This page was built for publication: Recursive Predicates and Quantifiers