数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究计算理论中的不可判定问题是什么？
在计算理论 (TOC) 中，对于那些我们无法构建算法，使其在无限时间内都能正确回答的问题，被称为不可判定问题。
如果不存在图灵机能够始终在无限时间内停止并回答“是”或“否”，则该问题是不可判定的。
示例
下面解释了不可判定问题的示例。这里，CFG 指的是上下文无关文法。
两个 CFG L 和 M 是否相等 - 由于我们无法确定任何 CFG 的所有字符串，因此我们无法预测两个 CFG 是否相等。
给定一个上下文无关语言，不存在图灵机 (TM) 能够始终在无限时间内停止并给出该语言是否模糊的答案。
给定两个上下文无关语言，不存在图灵机能够始终在无限时间内停止并给出这两个上下文无关语言是否相等的答案。
CFG 是否会生成输入字母表 (∑*) 的所有可能字符串是不可判定的。
停机问题
停机问题是不可判定问题中最著名的一个。
考虑以下代码
num=1;
while(num=0)
{
num=num+1;
}它会永远循环计数，因为它永远不会等于 0。这是一个停机问题的例子。
注意：每个上下文无关语言都是可判定的。
其他一些不可判定问题包括：
全域问题 - 确定任意 TM 是否在所有输入上都停止。这等价于判断一个程序对于任何输入是否可能进入无限循环的问题。它与停机问题不同，停机问题询问的是对于特定输入程序是否进入无限循环。
等价问题 - 确定两个 TM 是否接受相同的语言。这等价于判断两个程序是否对每个输入都计算出相同的输出的问题。
更新于： 2021年6月16日
12K+ 次浏览
广告