2024/04/17 by Sebastian Oberhoff, Oberhoff, Sebastian
Computer Science · #03F40 #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.2406.08494
openalex publication_date 2024/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The overarching theme of the following pages is that mathematical logic -- centered around the incompleteness theorems -- is first and foremost an investigation of computation, not arithmetic. Guided by this intuition we will show the following. * First, we'll all but eliminate the need for Gödel numbers. * Next, we'll introduce a novel notational device for representable functions and walk through a condensed demonstration that Peano Arithmetic can represent every computable function. It has achieved Turing completeness. * Continuing, we'll derive the Diagonal Lemma and First Incompleteness Theorem using significantly simplified proofs. * Approaching the Second Incompleteness Theorem, we'll be able to use some self-referential trickery to avoid much of the technical morass surrounding it; arriving at three separate versions. * Extending the analogy between the First Incompleteness Theorem and the Unsolvability of the Halting Problem produces an equivalent of the Nondeterministic Time Hierarchy Theorem from the field of computational complexity. * Lastly, we'll briefly peer into the realm of the uncomputable by connecting our ideas to oracles.