论文标题
三种计算模型及其等效性
Three computational models and its equivalence
论文作者
论文摘要
对计算性的研究起源于1900年希尔伯特的会议，他问的是一个相邻的问题，是为了确切地描述算法的概念。在寻找一个良好定义的过程中，出现了三个独立的理论：图灵和图灵机，戈德尔和递归功能，教堂和lambda演算。 后来，克莱恩（Kleene）确定了经典的计算模型是等效的。这一事实被许多教科书广泛接受，并且省略了证明，因为证明是乏味和不可读的。我们打算以现代的方式填补这一空白，而不会忘记数学细节。
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.
