turing-machines - 这种语言是可判定的、可识别的还是不可识别的？

Question

由所有图灵机描述 M 组成的语言 L，M 接受的语言是有限的。

我说 L 是一种可判定语言，因为我可以在函数 D(M) 上运行 M，如果在 M 的开始和接受状态之间存在循环，则返回 false，否则返回 true。

我感觉我错了，因为我低估了检测无限循环的难度。

感谢您的帮助，在此先感谢您。

Answer 1

如果你能决定这种语言，你就能决定停止问题。

假设 M 是一台机器，x 是它的输入。停止问题是说 M 是否在 x 上停止。考虑一台机器 N，它清除磁带并写入 x 来代替之前的任何输入。现在考虑通过运行 N 然后运行 ​​M 获得的机器。如果 M 接受 x，这台机器接受所有输入，否则不接受任何输入。如果你能说出任何机器接受的语言是否是有限的，你就能说出 M 是否在 x 上停止。但这是停止的问题。