Three computational models and its equivalence
This work provides a foundational resource for students and researchers in theoretical computer science by making a key but often omitted proof accessible.
The paper addresses the historical gap in presenting a clear proof of the equivalence between three classic computational models (Turing machines, recursive functions, and Lambda Calculus), offering a modern and detailed exposition.
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.