1

我有一个关于图灵机和停机问题的问题。

假设我们有 Atm = {(M,w)，其中 M 是图灵机，w 是输入}，
HALTtm = {(M,w)，其中 M 是图灵机，输入 w}

我想证明 HALTtm <=m Atm

我尝试了一些方法，但我认为它们远非解决方案。任何人都可以提供一些线索？

4

4 回答 4

2

好吧，请注意对于 HALTtm 中的所有 (M,w)，它一定是 (M,w) 在 Atm 中。然后显示存在一些 (M',w')，它是 Atm 的成员，但不会停止，因此不在 HALTtm 中。

于 2010-03-24T18:55:56.990 回答
0

对于以下每种语言，绘制接受该语言的图灵机的转换图。

  1. {aibj | i≠j}
于 2011-05-06T03:51:25.820 回答
0

<=m 是什么？我认为您的意思是“多一归约为”？在这种情况下，您要求的是一个总可计算函数 f ，对于所有字符串 x，

x 属于 HALTtm 当且仅当 f(x) 属于 Atm

如果存在这样的 f，我们可以确定停止问题：给定 x，计算 f(x) 并检查 f(x) 是否属于 Atm（Atm 很容易递归/可判定）。但是由于停止问题是不可判定的，所以这样的 f 不可能存在。所以 HALTtm不会多一还原为 Atm。

于 2011-12-06T14:00:14.480 回答
0

我们可以从 ATM 减少到 HALTTM 让 M2 是一台新机器，例如 On input x 当在 x 上运行 M2 如果 M2 接受 x 然后停止并接受如果 M2 拒绝然后 M2 进入无限循环

所以存在不会停止 M2 的斧头，所以 ATm 不在 HALTTM 中

于 2018-12-14T17:04:12.647 回答