What If Turing Had Preceded G\"odel?
<|reference_start|>What If Turing Had Preceded G\"odel?: The overarching theme of the following pages is that mathematical logic -- centered around the incompleteness theorems -- is first and foremost an investigation of $\textit{computation}$, not arithmetic. Guided by this intuition we will show the following.   * First, we'll all but eliminate the need for G\"odel 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.<|reference_end|>
@article{oberhoff2024what,
    title={What If Turing Had Preceded G\"odel?},
    author={Sebastian Oberhoff},
    journal={arXiv preprint arXiv:2406.08494},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.08494},
    primaryClass={cs.CC cs.LO}
}