浅谈可计算性与图灵机

摘要

一、引言本世纪初数理逻辑学家一直在探讨关于计算及可计算性的概念,1936年基本奠定了可计算性的理论基础。同年英国人图灵(A.M.Toring)也正式提出了图灵机。 40年代人们开始研制电子计算机时,可计算性理论与模型图灵机为电子计算机的研制提供了理论基础,特别是匈裔美籍数学家冯·诺依曼(Von·Neomann)对图灵机进行了改进并将它作为电子计算机的基本设计思想。目前电子计算机虽然已经历了四代的发展。