Java编程

图灵完备语言的区块链

如果了解过可“计算性理论”(Computability Theory)这个学术分支历史的读者会知道,在图灵机被提出之前其实就已经有了能模拟人类所能进行的全部计算过程的模型被设计出来。例如图灵在硕士阶段的导师,普林斯顿大学的阿隆佐·邱奇(Alonzo Church,1903-1995)教授于1928年就提出的“Lambda演算”就是其中之一。但图灵机相比起其他计算模型的优势在于它极为直观易于理解,而且很容易通过机械或者电子技术来实现。因此,图灵机的价值被人们所发现后,迅速成为了计算机解决“如何计算”问题的基础,在计算理论上也成为了可计算性的对标物。当一个新的计算模型出现,人们会判定它是否能解决所有在算法上可计算的问题,如果是的话,它就被称为是图灵等价或者图灵完备的。今天,我们称某种程序设计语言是图灵完备的,意思也是所有可计算的算法都能够用这种语言来实现(如今天常见的C、C++、Java、JavaScript等都是图灵完备的,而HTML/CSS这些语言则不是图灵完备的)。由于笔者是个程序员,所以这里就再多写一句题外话,由于图灵机的结构简单性,不考虑编码效率和可读性的话,只需寥寥几个操作指令就能照着图灵机的定义实现出一款图灵完备的语言,制造出脑洞大开的效果,大家有兴趣的话可以搜索一下“BrainFuck”和“Whitespace”这两门语言看看。

图灵完备语言的区块链

所谓图灵完备,就是一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的,图灵完备通常指具有无限存储能力的通用物理机器或编程语言。

简单来讲,一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。当然图灵完备也可能因为陷入死循环而导致程序崩溃。

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注