首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >递归可枚举语言与图灵完全语言的关系与区别?

递归可枚举语言与图灵完全语言的关系与区别?
EN

Software Engineering用户
提问于 2016-09-30 02:15:32
回答 1查看 1.1K关注 0票数 2

来自https://en.wikipedia.org/wiki/Recursively_可计数_语言

形式语言称为递归可枚举语言(也是可识别的、部分可判定的、半可分辨的、图灵可接受的或图灵可识别的),如果它是语言字母表上所有可能单词集合中的递归枚举子集,即如果存在图灵机,该机器将枚举语言的所有有效字符串。

来自https://en.wikipedia.org/wiki/Turing_完备性

数据操作规则系统(如计算机指令集、编程语言或元胞自动机)被认为是图灵完整的或计算通用的,如果它可以用来模拟任何单一的图灵机。

因此,递归可枚举语言和图灵完全语言都是用图灵机器定义的。

  1. 递归可枚举语言和图灵完全语言之间的根本区别是什么?例如,是否正确?
    • 一种递归枚举语言,图灵机的一组输入,以便它识别,同时
    • 图灵完整语言是图灵机提供的语言,还是它的等价语言?

那么,这两个概念是否属于图灵机的两个不相关的方面呢?

  1. 他们有什么关系?对于一种语言,
    • 递归枚举是否意味着图灵完成?
    • 是图灵完整是否意味着递归可枚举?

谢谢。

EN

回答 1

Software Engineering用户

发布于 2016-09-30 02:52:59

你的困惑源于过多的术语。“图灵完整语言”中的“语言”一词指的是一种编程语言,而在“递归可枚举语言”中,它指的是一种形式语言 --即在某些字母上形成的一组字符串。

所以当你说:

这两个概念属于图灵机的两个不相关的方面。

两者都在定义中使用图灵机器(至少在最常用的定义中),但它们不是同一类数学对象。这应该是(2)的。

为了澄清你的其他问题:

一种递归枚举语言,图灵机的一组输入,供它识别

是的,事实上,递归枚举语言也被称为图灵可识别语言.它们是可判定语言的严格超集。例如,停止的问题是可以识别的,但臭名昭著的是难以决定的。

图灵完整语言是图灵机提供的语言,还是它的等价语言?

形式上(-ish),图灵完全语言是一种能计算与图灵机相同的数论函数集(即函数N^k -> N)的语言。

另外,在未来,请试着问每个帖子一个问题。谢谢

票数 2
EN
页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://softwareengineering.stackexchange.com/questions/332403

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档