数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究图灵机中可识别和可判定之间的区别是什么？
当我们谈论图灵机 (TM) 时，它可以接受输入、拒绝输入或继续计算，这称为循环。
现在，当提供的输入属于该语言时，当且仅当图灵机接受该字符串时，语言才是可识别的。
此外，如果图灵机终止并拒绝字符串或根本不终止，则语言可以被识别。这意味着当提供的输入不属于该语言时，图灵机将继续计算。
而语言是可判定的，当且仅当存在一台机器，当提供的输入属于该语言时接受该字符串，而当提供的输入不属于该语言时拒绝该字符串。
示例
A = {hM, wi | M 是一个 DFA 且 w ∈ L(M)} 是可判定的。
A = {hM, wi | M 是一个 TM 且 w ∈ L(M)} 是可识别的。
图灵机中可识别和可判定的主要区别如下：
| 序号 | 图灵可识别 | 图灵可判定 |
|---|---|---|
| 1 | 如果存在一台机器只停机并接受该语言中的字符串，而不接受该语言之外的字符串，则该语言是图灵可识别的；对于不在该语言中的字符串，该图灵机要么拒绝，要么根本不停止。 | 如果存在一台机器接受语言中的字符串并拒绝语言之外的字符串，则称该语言是可判定的。 |
| 2 | 如果某个图灵机识别某个语言，则该语言称为图灵可识别。 | 如果某个图灵机判定某个语言，则该语言称为图灵可判定。 |
| 3 | 如果存在一个图灵机，当遇到该语言中的字符串时，该机器会终止并接受该字符串，那么我们可以说这种类型的语言是图灵可识别的。 | 如果存在一个图灵机，当遇到该语言中的字符串时，该机器会终止并接受该字符串，那么我们说这种类型的语言是图灵可判定的。 |
| 4 | 如果存在一个图灵机，当遇到该语言中不存在的字符串时，该机器要么终止并拒绝该字符串，要么根本不终止，那么我们可以说它是图灵可识别的。 | 如果存在一个图灵机，当遇到该语言中不存在的字符串时，该机器会终止并拒绝该字符串，那么我们可以说它是图灵可判定的。 |
| 5 | 它不是比图灵可判定更强的条件。 | 它是比图灵可识别更强的条件。 |
更新于：2021年6月16日
12K+ 次浏览
广告