图灵机和语言可决定性

Question

我正在阅读的文档在这里： 图灵机

在进行问题之前，以下是图片上使用的符号：

这里$ delta $表示空白，r，l和s表示右，向左移动头部，不移动它。也可以为图灵机绘制过渡图。状态由顶点表示，对于过渡$ delta（q，x）=（r，y，d）$，其中d代表r，l或s，用标签绘制q到r的弧线（x/ y，d）指示状态从q更改为r，当前正在读取的符号x已更改为y，并按照D的指示移动磁带头。

根据文件：

据说图灵机T可以决定一种语言L，并且仅当t写入“是”并停止字符串在l和t写入“否”时，如果字符串不在l中，则停止

这是三个例子：

• 情况1：

• 案例2：

• 案例3：

我只想验证我的理解。根据定义，在情况1和案例2中，其图灵机无法决定，因为机器无法分辨出无效的输入而不是{a}（例如AA，AAA，AAAA ....）是否在L中。

在情况2中，如果另一个A在第一个A之后出现，或者输入为空，则该机器将永远呈状态S和循环。

在情况3中，如果 a 被检测到，只有一个 a 存在，那 a 被取代 1 机器接受。否则， 0 被替换，输入不是在语言中决定的。

我对所有这些都有纠正吗？但是，在情况3中，如果我给出任何包含其他字符而不是的输入，该怎么办 a （例如字符串 ab, bc...）？还是说TM仅决定Turing Machine允许的一组字母$ Sigma $的语言？

如果一个比单个的弦 a （喜欢 aa, aaa,ab,bc...），机器可能会永远循环（如在情况2中）或停止而不接受（换句话说，它是“崩溃”的，它没有输入中的符号的过渡规则，例如 b 在上述图灵机中）。这也正确吗？

Answer 1

TM 决定 语言如果它进入 接受 语言中的单词状态，它进入 拒绝 说明如果不是。因此，它停止了所有输入。 笔记 上面定义的机器并非完全标准。他们表示接受和拒绝的方式是写$ 1 $或$ 0 $，然后进入停止状态。这等同于标准定义，但不优雅。

机器1不会拒绝语言中的单词。它只接受语言。

机器2不会停止使用语言中的单词。它只接受语言。

机器3拒绝，因此停止了语言中的单词，因此它决定了语言。