来自https://en.wikipedia.org/wiki/Recursively_可计数_语言
形式语言称为递归可枚举语言(也是可识别的、部分可判定的、半可分辨的、图灵可接受的或图灵可识别的),如果它是语言字母表上所有可能单词集合中的递归枚举子集,即如果存在图灵机,该机器将枚举语言的所有有效字符串。
来自https://en.wikipedia.org/wiki/Turing_完备性
数据操作规则系统(如计算机指令集、编程语言或元胞自动机)被认为是图灵完整的或计算通用的,如果它可以用来模拟任何单一的图灵机。
因此,递归可枚举语言和图灵完全语言都是用图灵机器定义的。
那么,这两个概念是否属于图灵机的两个不相关的方面呢?
谢谢。
发布于 2016-09-30 02:52:59
你的困惑源于过多的术语。“图灵完整语言”中的“语言”一词指的是一种编程语言,而在“递归可枚举语言”中,它指的是一种形式语言 --即在某些字母上形成的一组字符串。
所以当你说:
这两个概念属于图灵机的两个不相关的方面。
两者都在定义中使用图灵机器(至少在最常用的定义中),但它们不是同一类数学对象。这应该是(2)的。
为了澄清你的其他问题:
一种递归枚举语言,图灵机的一组输入,供它识别
是的,事实上,递归枚举语言也被称为图灵可识别语言.它们是可判定语言的严格超集。例如,停止的问题是可以识别的,但臭名昭著的是难以决定的。
图灵完整语言是图灵机提供的语言,还是它的等价语言?
形式上(-ish),图灵完全语言是一种能计算与图灵机相同的数论函数集(即函数N^k -> N)的语言。
另外,在未来,请试着问每个帖子一个问题。谢谢
https://softwareengineering.stackexchange.com/questions/332403
复制相似问题