Kef*_*fka 8 programming-languages
我听说过,如果程序员有足够的时间和技能,使用任何特定的语言和足够的代码行,那么任何程序都可以使用任何给定的语言创建.我知道它肯定不会具有成本效益,例如,在BASIC中重写Adobe Photoshop,但是一个足够好且耐心的程序员可能会用任何语言创建任何程序吗？
这取决于您如何定义"任何程序"和"任何语言".
让我们从第一个开始:"任何程序".有许多程序(事实上,有无限多的程序)不能被写入所有,无论是编程语言.最着名的一个是所谓的停机问题:写一个程序H,当给出任何程序P和任何输入时,x确定是否P(x)最终会停止.几十年前,阿兰图灵证明,这样的计划不可能存在.因此,你不能用任何编程语言编写这个程序.
现在,我们来谈谈"任何语言".实际上有不同类别的语言.有些人比其他人更强大.例如,正则表达式(它是一种编程语言)无法计算任何任意函数.它们的计算能力有限.但是,大多数通用编程语言通常称为"图灵完备".
历史简介:为了证明停机问题的不可判断性,Alan Turing发明了一种名为图灵机的假想机器.TM基本上是具有无限存储器的假设计算机,其计算特定功能.事实证明,您可以构建一个可以模拟任何其他图灵机的通用图灵机.
大约在同一时间,Alonzo Church发明了Lambda微积分.LC 也是一个抽象的计算数学模型,但完全不同.人们开始疑惑:这两个模型中哪一个更强大？UTM可以计算LC无法计算的任何内容,反之亦然吗？LC可以解决暂停问题吗？
事实证明,您可以为LC中的UTM编写模拟器,您可以构建一个解释LC的TM.这意味着TM可以计算LC可以计算的所有内容(通过简单地在解释器中运行),LC可以计算UTM可以计算的所有内容(通过在模拟器中运行它).所以,我们有
LC ? UTM ? UTM ? LC ? LC = UTM
在英语中:LC和UTM同样强大.其实,事实证明,所有的计算和模型每一个机器和每一个我们曾经发现的编程语言是在最强大的LC和UTM的确所有其他模式.这导致了所谓的Church-Turing-Thesis,它表明所有足够强大的计算模型同样强大,并且不存在比UTM或LC更强大的计算模型.(可能存在功能较弱的计算模型,例如正则表达式或总函数或仅具有有界循环的语言.)
我们将这种计算模型称为图灵完备.而且,顺便说一句,你不需要很多图灵完成.
因此,通过这种方式,我们现在可以定义"任何程序"和"任何语言"的含义:
如果程序可以用一种图灵完整语言编写,那么它可以用任何图灵完备语言编写.