scientific article

Publication date: 1984

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

independence proof theory incompleteness hierarchy recursive functions ordinals nested recursion subrecursion

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (only showing first 100 items - show all)

An analog characterization of the Grzegorczyk hierarchy ⋮ Reflection algebras and conservation results for theories of iterated truth ⋮ Souslin partitions of products of finite sets ⋮ How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study ⋮ On bimodal logics of provability ⋮ Computing queries with higher-order logics ⋮ A jump operator for subrecursion theories ⋮ Elementary descent recursion and proof theory ⋮ Time bounded rewrite systems and termination proofs by generalized embedding ⋮ Szemerédi's regularity lemma via martingales ⋮ Combinatory logic with polymorphic types ⋮ Natural Numbers and Infinitesimals ⋮ ALOGTIME and a conjecture of S. A. Cook ⋮ Iterated local reflection versus iterated consistency ⋮ Herbrand analyses ⋮ Squeezing Feasibility ⋮ Elementary functions and loop programs ⋮ Induction rules, reflection principles, and provably recursive functions ⋮ Elementary realizability ⋮ Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones ⋮ A time-space hierarchy between polynomial time and polynomial space ⋮ Dispensing with the continuum ⋮ An algebraic treatment of quantifier-free systems of arithmetic ⋮ A decidable theory of type assignment ⋮ Undecidable complexity statements in -arithmetic ⋮ Query languages for bags and aggregate functions ⋮ Sometimes slow growing is fast growing ⋮ Machine learning of higher-order programs ⋮ Transfinite induction within Peano arithmetic ⋮ Descriptive characterizations of computational complexity ⋮ A Uniform Approach to Fundamental Sequences and Hierarchies ⋮ Continued fractions of primitive recursive real numbers ⋮ Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) ⋮ Streamlined subrecursive degree theory ⋮ Unnamed Item ⋮ Strictly primitive recursive realizability, I ⋮ Monomial ideals and independence of ⋮ An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem ⋮ Pure Iteration and Periodicity ⋮ Linear logic and elementary time ⋮ Bounds on trees ⋮ Characterization of the Relations in Grzegorczyk's Hierarchy Revisited ⋮ Some Hierarchies of Primitive Recursive Functions on Term Algebras ⋮ A Model-Theoretic Approach to Ordinal Analysis ⋮ Minimal readability of intuitionistic arithmetic and elementary analysis ⋮ How to assign ordinal numbers to combinatory terms with polymorphic types ⋮ Parameter free induction and provably total computable functions ⋮ How to characterize provably total functions by local predicativity ⋮ Bimodal logics for extensions of arithmetical theories ⋮ Computable irrational numbers with representations of surprising complexity ⋮ On axiom schemes for \(T\)-provably \(\Delta_1\) formulas ⋮ Finitely stratified polymorphism ⋮ Local induction and provably total computable functions ⋮ Continuous-time computation with restricted integration capabilities ⋮ Things that can and things that cannot be done in PRA ⋮ Proof Theoretic Analysis by Iterated Reflection ⋮ A characterization of alternating log time by ramified recurrence ⋮ The Monotone Completeness Theorem in Constructive Reverse Mathematics ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths ⋮ Term rewriting theory for the primitive recursive functions ⋮ Fast growing functions based on Ramsey theorems ⋮ Bounded arithmetic for NC, ALogTIME, L and NL ⋮ Ordinal complexity of recursive definitions ⋮ Bounded linear logic: A modular approach to polynomial-time computability ⋮ Honest elementary degrees and degrees of relative provability without the cupping property ⋮ A sharpened version of McAloon's theorem on initial segments of models of \(I\Delta_ 0\) ⋮ Termination proofs by multiset path orderings imply primitive recursive derivation lengths ⋮ Subsystems of true arithmetic and hierarchies of functions ⋮ Minimum-complexity pairing functions ⋮ A Refinement of the μ-measure for Stack Programs ⋮ The scope of Gödel's first incompleteness theorem ⋮ Borel partitions of products of finite sets and the Ackermann function ⋮ A new recursion-theoretic characterization of the polytime functions ⋮ A survey of recursive analysis and Moore's notion of real computation ⋮ Expressibility of Higher Order Logics ⋮ Strictly orthogonal left linear rewrite systems and primitive recursion ⋮ Long finite sequences ⋮ The Ackermann functions are not optimal, but by how much? ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ The complexity of decision procedures in relevance logic II ⋮ On Brouwer's continuity principle ⋮ Unnamed Item ⋮ Sub-computabilities ⋮ Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations ⋮ Termination proofs by multiset path orderings imply primitive recursive derivation lengths ⋮ Complexity Hierarchies beyond Elementary ⋮ Primitive Recursive Bounds for Van Der Waerden Numbers ⋮ On the computational complexity of imperative programming languages ⋮ Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian ⋮ Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity ⋮ Unprovability results for clause set cycles ⋮ A predicative and decidable characterization of the polynomial classes of languages ⋮ Maximal machine learnable classes ⋮ Classifying the Provably Total Functions of PA ⋮ Notations for exponentiation. ⋮ Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions ⋮ Critical points in an algebra of elementary embeddings ⋮ Modular tree transducers ⋮ Dedekind cuts and long strings of zeros in base expansions

This page was built for publication: