数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究可判定问题和不可判定问题解释
在了解计算理论 (TOC) 中的可判定问题和不可判定问题之前，我们必须先了解可判定语言和不可判定语言。因此，让我们首先看看可判定语言是什么意思。
可判定语言
如果存在一个判定器 M 使得 L(M) = L，则语言 L 称为可判定的。
给定一个判定器 M，您可以了解字符串 w 是否属于 L(M)。
在 w 上运行 M。
尽管可能需要很长时间，但 M 最终会接受或拒绝 w。
集合 R 是所有可判定语言的集合。
如果 L 可判定，则 L ∈ R。
不可判定语言
如果所有“是”实例到问题 P 的语言 L 不可判定，则决策问题 P 不可判定。
不可判定语言可能是部分可判定的，但不是可判定的。假设，如果一种语言甚至不是部分可判定的，那么对于该语言不存在图灵机。
问题
确定下面给出的问题是可判定的还是不可判定的。
“假设给定的输入是一些图灵机 M 和一些字符串 w。问题是要确定机器 M 在输入字符串 w 上执行时，其读写头是否会连续三次连续向左移动。”
解决方案
定义 M' 是一个图灵机，它以 (M,w) 为输入，其中 M 是 M' 识别的图灵机，w 是 M 的输入。
每当模拟的机器 M 在处理输入 w 时将读写头向左移动时，M' 停止并接受 (M,w)。
对于 M' 的特定输入 (M,w)，构造图灵机 P 为 -
P 在 (M,w) 上执行 M'
如果 M' 接受 (M,w)，则 P 停止并接受任何输入。
我们试图将通用图灵机 U 归约到 P，因为我们知道 L(U) 不可判定，并且我们也得出结论 L(P) 不可判定。因此，M' 不可判定。
证明是通过反证法。
假设这个问题是可判定的，然后我们必须证明改变图灵机 (ATM) 也是可判定的 -
ATM = {M 是一个 TM，并且 M 接受 w}。
设 R 是一个判定左端问题的图灵机。
也就是说，R 决定语言
leftmost = {M 在输入 w 上尝试将读写头移到最左侧磁带单元格时，其读写头位于最左侧磁带单元格}。
现在，想法是构造一个图灵机 S，它以这样一种方式决定 ATM，即它使用 R。
在输入时，S 首先将机器 M 修改为 M'，以便仅当 M 接受其输入时，M' 才将其读写头从最左侧单元格向左移动。
为了确保在计算过程中，M' 不会从最左侧位置向左移动读写头，
首先，机器 M' 将输入 w 向右移动一个位置，并在最左侧磁带单元格上放置一个特殊符号。M' 的计算从读写头位于第二个磁带单元格开始。
在计算过程中，M' 尝试将其读写头移动到最左侧磁带单元格时，M' 通过读取特殊符号来发现这一点，并将读写头放回第二个单元格，并继续执行。如果 M 进入接受状态，则 M' 进入一个循环，迫使读写头始终向左移动。
在 S 构造完 M' 后，它在输入 <M'; w> 上运行判定器 R。
如果 R 接受，则 S 接受，否则如果 R 拒绝，则 S 拒绝。
因此，ATM 是可判定的，这是一个矛盾。
10K+ 次查看
