Cover Image

What If Turing Had Preceded Gödel?

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Oberhoff, Sebastian
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Logic in Computer Science 03F40 F.4.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

Deducibility in the full Lambek calculus with weakening is HAck-complete
by: Greati, Vitor, et al.
Published: (2024)

Hypersequent Calculi Have Ackermannian Complexity
by: Balasubramanian, A. R., et al.
Published: (2026)

Glivenko's theorems from an ecumenical perspective
by: Pereira, Luiz Carlos, et al.
Published: (2026)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

A Guide to Krivine Realizability for Set Theory
by: Matthews, Richard
Published: (2023)

How to play the Accordion: Uniformity and the (non-)conservativity of the linear approximation of the λ-calculus (extended version)
by: Cerda, Rémy, et al.
Published: (2023)

Finitary Simulation of Infinitary $β$-Reduction via Taylor Expansion, and Applications
by: Cerda, Rémy, et al.
Published: (2022)

Proof Compression via Subatomic Logic and Guarded Substitutions
by: Barrett, Victoria, et al.
Published: (2025)

On Godel's treatment of the undecidable in 1931
by: Cattabriga, Paola
Published: (2024)

A proof complexity conjecture and the Incompleteness theorem
by: Krajicek, Jan
Published: (2023)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic
by: Barroso-Nascimento, Victor, et al.
Published: (2025)

Cut elimination for propositional cyclic proof systems with fixed-point operators
by: Hori, Hiromasa, et al.
Published: (2023)

Gödel coding on fibrations and geminal categories
by: Ikeda, Yuto
Published: (2026)

Thoughts on sub-Turing interactive computability
by: Japaridze, Giorgi
Published: (2024)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

Coinductive proof search for polarized logic with applications to full intuitionistic propositional logic
by: Santo, José Espírito, et al.
Published: (2020)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

The Orientation Boundary for Step-Duplicating Recursors: Mechanized Impossibility, Escape, and Certification
by: Rahnama, Moses
Published: (2025)

Fractal Analysis on the Real Interval: A Constructive Approach via Fractal Countability
by: Semenov, Stanislav
Published: (2025)

Internal Effectful Forcing in System T
by: Escardo, Martin H., et al.
Published: (2025)

Complexity of Nonassociative Lambek Calculus with classical logic
by: Płaczek, Paweł
Published: (2024)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
by: Ito, Sohei, et al.
Published: (2026)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Hereditary First-Order Logic: the tractable quantifier prefix classes
by: Bodirsky, Manuel, et al.
Published: (2024)

On the Computational Power of Extensional ESO
by: Bodirsky, Manuel, et al.
Published: (2025)

Symmetries in Sorting
by: Choudhury, Vikraman, et al.
Published: (2025)

Effective bases and notions of effective second countability in computable analysis
by: Brattka, Vasco, et al.
Published: (2025)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Computation as a Game
by: Bilokon, Paul Alexander
Published: (2025)

Forcing with Language Fragments, Extending Namba Forcing, and Models of Theories with Constraints in Interpretation
by: Lau, Desmond
Published: (2024)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

Y is a least fixed point combinator
by: Helfer, Joseph
Published: (2025)

Structural focalization
by: Simmons, Robert J.
Published: (2011)

On Some Complexity Results for Even Linear Languages
by: Cojocaru, Liliana
Published: (2024)

Punctually Standard and Nonstandard Models of Natural Numbers
by: Bazhenov, Nikolay, et al.
Published: (2026)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)

Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof
by: Borzechowski, Manfred, et al.
Published: (2025)

Finite Hilbert systems for Weak Kleene logics
by: Greati, Vitor, et al.
Published: (2024)