图灵机停机问题
我有一个关于图灵机和停止问题的问题。
假设我们有 Atm = {(M,w)，其中 M 是图灵机，w 是输入} 且
HALTtm = {(M,w) 其中 M 是图灵机，输入 w 时停止}
我想证明 HALTtm <=m Atm
我已经尝试了一些方法，但我认为它们距离解决方案还很远。 任何人都可以提供一些线索吗？
I have a question about turing machines and halting problem.
Suppose that we have Atm = {(M,w) where M is a turing machine and w is an input} and
HALTtm = {(M,w) where M is a turing machine halts with an input w}
I want to prove that HALTtm <=m Atm
I've tried some methods but I think they're far from the solution.
Anyone can give some clues ??
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
好吧，观察到对于 HALTtm 中的所有 (M,w)，Atm 中一定存在 (M,w)。然后表明存在一些 (M',w')，它是 Atm 的成员但不会停止，因此不在 HALTtm 中。
Well, observe that for all (M,w) in HALTtm, it must be that (M,w) is in Atm. Then show there exists some (M',w') which is a member of Atm but which does not halt, and so is not in HALTtm.
什么是<=m？我认为你的意思是“多一减少到”？在这种情况下，您要求的是一个总可计算函数 f ，这样对于所有字符串 x，
如果这样的 f 存在，我们可以决定停止问题：给定 x，计算 f(x) 并检查 f(x) 是否属于 Atm（Atm 很容易递归/可判定）。但由于停机问题不可判定，因此这样的 f 不可能存在。因此，HALTtm 不会将多对一简化为 Atm。
What is <=m? I think you mean "many-one reduces to"? In that case, what you're asking for is a total computable function f such that for all strings x,
If such an f existed, we could decide the halting problem : given x, compute f(x) and check if f(x) belongs to Atm (Atm is easily recursive/decidable). But since the halting problem is not decidable, such an f cannot exist. So HALTtm does not many-one reduce to Atm.
对于以下每种语言，为接受该语言的图灵机绘制转换图。
For each of the following languages, draw a transition diagram for a Turing Machine that accepts that language.
{aibj | i≠j}我们可以从 ATM 减少到 HALTTM
让M2像新机器一样
输入 x
当在 x 上运行 M2 时
如果 M2 接受 x 则停止并接受
如果 M2 拒绝，则 M2 进入无限循环
，因此存在不停止 M2 的 ax，因此 ATm 不在 HALTTM 中
we can do reduction from ATM to HALTTM
let M2 is a new machine like
On input x
When run M2 on x
if M2 accepts x then halt and acccept
if M2 rejects then M2 goes for an infinite loop
so there exists a x that not halts M2 so ATm is not in HALTTM