Three computational models and its equivalence

Por • 18 nov, 2020 • Sección: Filosofía

Ciro Ivan Garcia Lopez

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.

arXiv:2010.15600v1 [cs.LO]

Logic in Computer Science (cs.LO); Computational Complexity (cs.CC); Computation and Language (cs.CL); General Literature (cs.GL)

Post to Twitter

Escribe un comentario