最小的图灵完备语言

#最小的图灵完备语言| 来源: 网络整理| 查看: 265

最小的图灵完备语言——BrainFuck

图灵完备性(Turing completness)

在可计算性理论(computability theory)中，图灵等价指的是：对于两个计算机A和B，如果A可以模拟B，B可以模拟A，就称他们是图灵等价的。

根据“丘奇-图灵”理论，图灵机是表达能力最强大的计算系统，对现实世界中的任何计算机，都可以用图灵机[1]来模拟它。腻不腻害！

如果某个系统能够模拟图灵机，那么就称该系统是图灵完备的。

可不是，都能完全模拟图灵机了可不是就完备了。

图灵完备语言

套用上面的定义，如果一个编程语言可以完全模拟图灵机，那么它就是图灵完备的。

图灵机的定义是很简单的，仅有少量操作和一种数据类型。所以很容易验证某一个语言是图灵完备的。写个模拟器呗。

大部分编程语言都是图灵完备的，因为他们需要解决各种问题的通用能力，而这正是图灵机所具备的。确实存在一些语言不是图灵完备的，他们通常是被设计用来解决某些特殊的问题，比如，你猜对了，SQL[2]以及正则表达式。

以经验来看，凡带有分支，跳转能力，并且支持数组状数据结构的语言基本上就是图灵完备的。

BrainFuck

下面是由BrainFuck写的一段小程序quine:

->+>+++>>+>++>+>+++>>+>++>>>+>+>+>++>+>>>>+++>+>>++>+>+++>>++>++>>+>>+>++>++>+>>>>+++>+>>>>++>++>>>>+>>++>+>+++>>>++>>++++++>>+>>++>+>>>>+++>>+++++>>+>+++>>>++>>++>>+>>++>+>+++>>>++>>+++++++++++++>>+>>++>+>+++>+>+++>>>++>>++++>>+>>++>+>>>>+++>>+++++>>>>++>>>>+>+>++>>+++>+>>>>+++>+>>>>+++>+>>>>+++>>++>++>+>+++>+>++>++>>>>>>++>+>+++>>>>>+++>>>++>+>+++>+>+>++>>>>>>++>>>+>>>++>+>>>>+++>+>>>+>>++>+>++++++++++++++++++>>>>+>+>>>+>>++>+>+++>>>++>>++++++++>>+>>++>+>>>>+++>>++++++>>>+>++>>+++>+>+>++>+>+++>>>>>+++>>>+>+>>++>+>+++>>>++>>++++++++>>+>>++>+>>>>+++>>++++>>+>+++>>>>>>++>+>+++>>+>++>>>>+>+>++>+>>>>+++>>+++>>>+[[->>+[-[-]>]

【本文地址】

公司简介

联系我们