为什么计算机科学存在图灵机和Lambda演算两种世界观?

计算机科学存在两种世界观:图灵机和Lambda演算,它们指出了到达图灵完备的两条技术路线。但是量子力学中却存在着三种世界图景:薛定谔图景,海森堡图景和狄拉克图景。为什么计算机科学有两种基本世界观,但是量子力学却存在三种世界图景?它们之间是否存在什么对应关系?

实际上,计算机科学中实现图灵完备的基本技术路线也可以被看作是有三条,它们和量子力学的世界图景存在如下对应关系:    

        图灵机<=> 薛定谔图景    

       Lambda演算 <=> 海森堡图景    

        可逆计算 <=> 狄拉克图景

以下是具体的分析。首先,量子力学中最基本的世界图景同样是两个,狄拉克图景是前两种图景自然衍生的结果    

薛定谔图景中算子固定,态函数演化    

海森堡图景中态函数固定,而算子演化    

狄拉克图景(相互作用图景)中态函数和算符都不固定,它们都随时间演化

在狄拉克图景中,我们将系统的Hamiltion量拆分为已知的部分和待研究的微小扰动   

       H = H_0 + H_1

然后研究系统如何偏离已知模型进行演化,即我们所关心的是差量描述的演化情况。在相互作用图景下,态函数和算符都随时间演化。

如果把量子力学和计算机理论做个对比,我们会发现量子力学中的世界图景和计算机理论的世界观之间存在一个有趣的对应关系。   

 图灵机是一种结构固化的机器,它具有可枚举的有限的状态集合,只能执行有限的几条操作指令,但是可以从无限长的纸带上读取和保存数据。例如我们日常使用的电脑,它在出厂的时候硬件功能就已经确定了,但是通过安装不同的软件,传入不同的数据文件,最终它可以自动产生任意复杂的目标输出。图灵机的计算过程在形式上可以写成 

   目标输出 = 固定的机器 (无限复杂的输入)

与图灵机相反的是,lambda演算的核心概念是函数,一个函数就是一台小型的计算机器,函数的复合仍然是函数,也就是说可以通过机器和机器的递归组合来产生更加复杂的机器。lambda演算的计算能力与图灵机等价,这意味着如果允许我们不断创建更加复杂的机器,即使输入一个常数0,我们也可以得到任意复杂的目标输出。      

  目标输出 = 无限复杂的机器(固定的输入)

计算机科学中的两个基本理论在形式上都可以被表达为 Y = F(X)这样一种抽象的形式。如果仿照狄拉克图景的导出过程,我们认识到在真实的物理世界中,人类的认知总是有限的,所有的量都需要区分已知的部分和未知的部分,因此我们需要进行如下分解:       

    Y = F(X) = (F0+F1)(X0+X1) = F0(X0) + Delta

翻译为具体的软件实现,可以得到如下软件构造公式      

     App = Delta x-extends Genertor<DSL>

完整介绍参见知乎文章 https://www.zhihu.com/question/614938288/answer/3147722439

站务

全部专栏