2020/10/26 by Ciro Ivan Garcia Lopez, Lopez, Ciro Ivan Garcia
Computer Science · #Computability, Logic, AI Algorithms #Computation and Language (cs.CL) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2010.15600
openalex publication_date 2020/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The study of computability has its origin in Hilbert's conference of 1900, where an adjacent question, to the ones he asked, is to give a precise description of the notion of algorithm. In the search for a good definition arose three independent theories: Turing and the Turing machines, Gödel and the recursive functions, Church and the Lambda Calculus. Later there were established by Kleene that the classic models of computation are equivalent. This fact is widely accepted by many textbooks and the proof is omitted since the proof is tedious and unreadable. We intend to fill this gap presenting the proof in a modern way, without forgetting the mathematical details.