图灵和图灵机

什么是计算?广义上讲,一个函数变换,把输入信息 x 变成输出信息 f(x)就是一个计算!如果我们把一个小球扔到地上,小球又弹起来了,你完全可以把小球的运动都抽象成一些诸如位置、速度、形状等等信息,而地面把小球弹起来就无非是对小球的这些信息进行了某种变换,因而地面就完成了一次计算! 自然中的一切过程都是在进行计算,碰撞的小球、流动的溪水、燃烧的火焰,大自然用自己的方式处理着大量的信息。如同在《黑客帝国》中一样,我们所生活的世界是计算出来的。著名的Mathematica 软件发明人沃尔弗莱姆(Wolfram)甚至宣称,整个宇宙就是一台大的图灵计算机。而美国ACM颁发的计算机领域最高荣誉是“图灵奖”。 究竟什么是图灵机?图灵又是何方神圣?本文先景仰一下天才图灵,再了解一下图灵机的基本思想,然后看看图灵机是如何工作的。