The Wayback Machine - https://web.archive.org/web/20221028225806/https://baike.sogou.com/kexue/d10222.htm

递归可枚举语言

编辑

在数学、逻辑和计算机科学中,如果一种形式语言是该语言字母表上所有可能单词集合中的一个递归可枚举子集,即如果存在一个将枚举该语言所有有效字符串的图灵机,则称之为递归可枚举(也可识别、部分可判定、半可判定、图灵可接受或图灵可识别)。

递归可枚举语言在形式语言的乔姆斯基(Chomsky)层次结构中被称为类型0语言。所有规则的、无上下文的、上下文敏感的和递归的语言都是递归可枚举的。

所有递归可枚举语言的类都被称为RE。

1 定义编辑

递归可枚举语言有三种等价定义:

1.递归可枚举语言是该语言字母表上所有可能单词集合中的递归可枚举子集。

2.递归可枚举语言是一种形式语言,它有一个图灵机(或其他可计算函数)来枚举该语言的所有有效字符串。请注意,如果语言是无限的,则可以选择提供的枚举算法以避免重复,因为我们可以测试为数字n生成的字符串是否已经为小于n的数字生成。如果已经生成,则改用输出作为n+1的输入 (递归),但是需要再次测试它是否是“新的”。

3.递归可枚举语言是一种形式语言,对于这种语言存在一种图灵机(或其他可计算函数) 将暂停并接受任何字符串作为输入,但当以非语言字符串呈现时,可能会暂停并拒绝或进入死循环。这些要求与递归语言相比是相反的,因为递归语言要求图灵机在任何情况下都可以随时停机。

所有常规的、上下文无关的、上下文敏感的和递归语言都是递归可枚举的。

波斯特(Post)定理表明,RE及其补码co-RE对应于算术层次的第一级。

2 例子编辑

停机的图灵机集合是递归可枚举的,但不是递归的。事实上,人们可以运行图灵机,并接受机器停止,因此它是递归可枚举的。另一方面,这个问题是无法确定的。

其他一些非递归的递归可枚举语言包括:    

  • 邮件通信问题(Post correspondence problem)
  • 死亡率(Mortality (computability theory))
  • 可判定性 (Entscheidungsproblem)

3 闭合属性编辑

递归可枚举语言(REL)在以下操作中关闭。也就是说,如果 LP 是两种递归可枚举的语言,那么下列语言也是递归可枚举的:

  • 克林星符号,   关于 L
  • 串联,   关于 LP
  • 联合,  
  • 交叉,  

递归可枚举语言在集合差或互补下是不封闭的。设定差异 L − P 可以递归枚举,也可以不递归枚举。 如果 L 是递归可枚举的,那么有当且仅当 L 递归时,L的补集也是递归的。

阅读 78
版本记录
  • 暂无