数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究证明递归语言在反转运算下是封闭的？
考虑一个在字母表 T 上的语言 L，如果存在一个图灵机 (TM) 生成一个数字序列 T*，并且该序列恰好包含 L 的所有成员，则称该语言为递归可枚举的。
而 L 被称为递归的，如果存在一个图灵机列出 L 的所有成员，并在每个成员作为输入时停止。
因此，从以上陈述可以清楚地看出，每个递归语言也是递归可枚举的，但反之则不成立。
语言家族之间精确的关系如下所示。
定理
步骤 1 - 在字母表 T 上，一个语言 L 被称为递归的，当且仅当 L 及其相对于 T* 的补集 L 都是递归可枚举的。
步骤 2 - 语言 L 的反转 L^(R) 是 T* 中所有元素的字符串的集合，我们可以通过将 L 中所有元素按反序排列得到。
步骤 3 - 让我们考虑一个递归可枚举的语言 L，其所有元素都由图灵机 M 列出。
步骤 4 - 现在我们可以设计另一个图灵机 M'，其接受的字符串是 L 中成员的反转字符串。
步骤 5 - 这也符合丘奇-图灵论题，该论题指出每个有效的计算过程也可以由一些图灵机完成。
步骤 6 - 现在，从以上讨论可以清楚地看出，如果 L 是递归可枚举的，那么其反转 L^(R) 也是递归可枚举的。
步骤 7 - 如果 T* 中的字符串 X 属于 (L^(R))'，当且仅当 X 不属于 L^(R)，这显然意味着当且仅当 X^(R) 的反转不属于 L，这进一步意味着 X^(R) 属于 L' ⇔ X 属于 l^(R)。
即 (L^(R))' = L'^(R)
结论
如果 L 是递归的，则 L'(R) 及其补集 (L^(R))' 也是递归可枚举的，这进一步意味着 L^(R) 的反转也是递归的。
更新于： 2021年6月16日
630 次浏览
广告