递归语言

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

递归语言

递归语言在数学、逻辑和计算机科学中，递归语言或递回语言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。定义. 递归语言有两种等价的主要定义: 递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。设 "S" ⊆ Σ* 是一个语言，"M" 是一台图灵机，若对于任何字符串 ω ∈ Σ*，有则称 "M" 判定语言 "S"。若存在这样的 "M"，"S" 就称为图灵可判定语言。闭包性质. 递归语言是在下列运算下是闭合的。就是说，如果 "L" 和 "P" 是两个递归语言，则下列语言也是递归的: 图灵可判定语言与图灵可识别语言的关系. 注意图灵可判定语言和图灵可识别语言的区别：若 "S" 是图灵可识别语言，则只需存在一台图灵机 "M"，当 "M" 的输入 ω ∈ "S" 时，"M" 一定会停机并进入接受状态；当 "M" 的输入 ω ∉ "S" 时，"M" 可能停机并进入拒绝状态，或者永不停机。而若 "S" 是图灵可判定语言，则必须存在图灵机 "M" ，使得对于任意输入串 ω ∈ Σ*，"M" 总能停机，并根据 ω 属于或不属于 "S" 分别进入接受或拒绝状态。定理：存在图灵不可判定语言。证明：定义语言 HALTING 如下： HALTING = { | "M" 是一台图灵机，"x"是一个字符串，且"M"在输入"x"上可以停机} 其中表示将 "M" 的编码和串 "x" 以某种方式配对而得到的串。可以证明 HALTING 是图灵不可判定语言，参见停机问题。 Q.E.D. 下列定理表明了图灵可判定语言和图灵可识别语言的关系。定理：一个语言是图灵可判定的当且仅当它和它的补语言都是图灵可识别的。证明：若 "S" 是图灵可判定的，显然 "S" 和 "S" 的补都是图灵可识别的。下面假设存在图灵机 "M"1 和 "M"2 分别识别"S" 和 "S" 的补，我们可以构造一个图灵机 "M" 如下： "M" = 对于输入 ω 很显然，对于任何 ω，它要么属于"S"，要么属于 "S" 的补，所以 "M"1 和 "M"2 中必然有且仅有一个可以在有限步执行内接受 ω 。若 "M"1 在 "k" 步内接受 ω，说明 ω 属于 "S"，则当 "i" = "k" 时，"M" 会接受 ω 并停机；同理，若 "M"2 在 "k" 步内接受 ω，说明 ω 属于 "S" 的补，则当 "i" = "k" 时， "M" 会拒绝 ω 并停机。于是 "M" 就判定了语言 "S"。 Q.E.D. 根据上述定理直接可得下述引理：定理： HALTING 的补语言是图灵不可识别的。证明：很显然 HALTING 是图灵可识别语言，若它的补语言也是图灵可识别的，则根据上述定理知 HALTING 是图灵可判定的，这和停机问题中证明的结论矛盾。

欧洲冠军联赛

北京工商大学

窦唯

北京时间

英王乔治五世级战列舰 (1939年)

新华网

魏延

文森特·梵高

硫

保罗·塞尚

向日葵

五虎将