我读过"什么是图灵完整"和维基百科页面,但我对正式证据不太感兴趣,而不是图灵完全的实际意义.
我实际上要确定的是,我刚刚设计的玩具语言是否可以用作通用语言.我知道我可以证明我是否可以用它来编写图灵机.但是,在我确信成功之前,我不想进行这项运动.
有没有最低限度的功能,没有图灵完整性是不可能的？是否有一系列功能几乎可以保证完整性？
(我的猜测是条件分支和可读/可写的内存存储将使我的大部分方式)
编辑:
我想我已经说过"图灵完成"了.我试图以合理的信心猜测具有特定功能集的新发明的语言(或者具有特定指令集的VM)将能够计算任何值得计算的东西.我知道证明你可以用它建立图灵机是一种方式,但不是唯一的方法.
我所期待的是一套类似的准则:"如果可以做X,Y和Z,它可以或许做任何事情".
你需要某种形式的动态分配结构(的malloc或new或cons会做),要么递归函数或写一个无限循环的其他方式.如果你有这些并且可以做任何有趣的事情,你几乎肯定是图灵完成的.
lambda演算与图灵机相当,如果你实现lambda演算,写lambda演算程序实际上非常有趣. 路比图灵机编写程序的更多乐趣!
我所知道的图灵完全性的唯一实际意义是你可以编写不终止的程序.我使用了一些保证终止的特殊用途语言,因此不是图灵完备的.有时放弃额外的表达能力以换取有保证的终止是有用的.
"图灵完整性"描述了能够表达任意算法计算的属性,这首先是图灵机器的重点.如果语言或逻辑系统具有此属性,则可将其描述为"图灵完成".从实际角度来看,所有通用编程语言 - 以及令人惊讶的大量特殊目的 - 都可以通过适当宽松的定义来实现(见下文).
但是,对图灵完整性的严格定义意味着无限的存储容量,这当然在物理上是不可能的.鉴于此,没有物理机器可能是图灵完成,但是当将图灵完整性归因于编程语言时,这种约束通常是放松的(至少是非正式的).对语言的图灵完整性的一个简单测试是该语言是否可用于实现图灵机模拟器.
一个非图灵完备的广泛系统的例子是关系代数,这是SQL背后的理论基础,如Codd的论文中描述的大型共享数据库的关系模型. 关系代数具有Godel完整性的属性,这意味着它可以表达任何可以根据一阶谓词演算(即普通逻辑表达式)定义的计算.但是,它不是Turing-Complete,因为它无法表达任意算法计算.
请注意,大多数(如果不是全部)所有实用SQL方言都将纯关系模型与过程构造扩展到通常应用于编程语言的定义为图灵完成的程度.但是,单个SQL查询基本上不是.
Turing Complete特定于域的语言的一些更令人震惊的例子是TeX和sendmail.cf , . 在后一种情况下,实际上有一个着名的例子,有人使用sendmail.cf来实现通用的图灵机模拟器.
如果你能用你的语言写一个Brainf $&# interpreter,那就是Turing-complete. 事实证明,LOLCODE正是以图灵完成的方式完成的.
非图灵完备的语言示例经常具有有界循环,例如:
for i=1 to N {...}
但缺乏无限循环,检查更一般的条件,如:
while bool_expr {...}
如果所有可能的循环结构都有界限,那么您的程序将保证终止.并且,尽管无条件终止保证可能有用,但它也表明该语言不是图灵完备的.
还要注意,确定所有可能的循环结构可能很困难; 例如,我很确定C++模板并不打算成为Turing-complete ......
我不确定是否存在"最小功能集",但为了证明语言是图灵完整的,您只需要证明它可以模拟另一个图灵完整系统(不一定是图灵机),只要已知其他系统是图灵完整的.http://en.wikipedia.org/wiki/Turing_complete#Examples列出了图灵完整系统的完整列表.其中一些比图灵机更简单.
京公网安备 11010802040832号 | 京ICP备19059560号-6 
