问题标签 [halting-problem]

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

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

我想证明 HALTtm <=m Atm

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

我试图找到逻辑上的艾伦图灵解释为什么不能有一个程序来检查另一个程序。

我记得我们在计算课程上学过，但现在我找不到解决方案，我需要向工作中的某个人解释。

感谢帮助。

只是在阅读关于模拟器和声明的高度投票问题

已经证明，找到给定二进制文件中的所有代码等价于停机问题。

真的对我出手了。

这肯定不是真的吗？它不只是一个大的依赖图吗？

非常感谢您对此声明的进一步了解。

我正在尝试在 Android 3.0 模拟器上测试一个简单的状态栏通知程序。
当我尝试从 Eclipse 运行我的应用程序时，有时我会看到一条消息，apk can't be installed当我检查 DDMS 日志时，我会看到 javaoutOfMemory错误。虽然我的应用程序相当简单，但只有一个 java 文件。

有时当我启动模拟器时，它会完全关闭我的窗口。我也对此进行了Windows XP测试Ubuntu。当Ubuntu模拟器即将完全启动并显示主页时，我的操作系统也崩溃了。

任何其他版本的 Android 都可以在我的 PC 上正常运行2.2，例如2.3. 3.0我仅在（蜂窝）版本中看到此问题。对此有什么解决办法吗？

谢谢马尼什
_

检测确定性程序（即状态机）是否处于等效于解决停机问题的无限循环中？

我想出了一个解决方案，但我不确定为什么它不应该工作：

• 让程序运行
• 当您认为它处于无限循环中时，请定期对其内存进行快照
• 如果您检测到相同的快照，则程序处于无限循环中
• 只要您没有两次获得相同的快照，它要么（1）不在无限循环中，要么（2）您需要更快地拍摄快照（也许每次内存访问一次？）

我假设这不起作用……但是为什么呢？

这似乎是检测程序是否处于无限循环中的一种完全合理的方法（例如，特别是如果您存储哈希而不是内存本身，尽管这不会 100% 准确）......它有什么问题，如果有的话？

在这个关于 NP、NP-hard 和 NP-complete 定义的问题的回答中，Jason 声称

停止问题是经典的 NP-hard 问题。这是给定程序 P 和输入 I 的问题，它会停止吗？这是一个决策问题，但它不在 NP 中。很明显，任何 NP 完全问题都可以简化为这个问题。

虽然我同意停机问题在直觉上是一个比 NP 中的任何问题都“更难”的问题，但老实说，我无法提出一个正式的数学证明来证明停机问题是 NP 难的。特别是，我似乎无法找到从 NP 中的每个问题（或至少任何已知的 NP 完全问题）的实例到停止问题的多项式时间多对一映射。

是否有直接的证据证明停机问题是 NP 难的？

我读过一些关于大哦计算和停机问题的文章。显然，所有算法都不可能说它们是否会停止，例如：

但是，这样的程序有什么大不了的呢？我认为它没有定义，出于同样的原因，也无法说它是否会停止。你不知道。

所以......有一些可能的算法，你不能说它是否会停止。但是，如果你不能说，那么该算法的大问题是未定义的。

现在到我的观点，计算一个软件的大哦。为什么你不能写一个程序来做到这一点？因为它要么是一个函数，要么是未定义的。

另外，我没有说任何关于编程语言的事情。纯函数式编程语言呢？可以在那里计算吗？

我正在查看Sipser的计算理论简介中的停止问题的证明，我主要关心的是以下证明：

如果 TM M 不知道它何时循环（它不能接受或拒绝，这就是为什么 TM 对所有字符串都是图灵可识别的），那么决策者 H 将如何确定 M 是否可能处于循环中？当 TM D 进行处理时，同样的问题将继续存在。

Look at the following infinite while loop in Java. It causes a compile-time error for the statement below it.

The following same infinite while loop, however works fine and doesn't issue any errors in which I just replaced the condition with a boolean variable.

In the second case also, the statement after the loop is obviously unreachable because the boolean variable b is true still the compiler doesn't complain at all. Why?

Edit : The following version of while gets stuck into an infinite loop as obvious but issues no compiler errors for the statement below it even though the if condition within the loop is always false and consequently, the loop can never return and can be determined by the compiler at the compile-time itself.

Edit : Same thing with if and while.

The following version of while also gets stuck into an infinite loop.

This is because the finally block is always executed even though the return statement encounters before it within the try block itself.

是否可以构造一个高阶函数isAssociative，它接受另一个有两个参数的函数并确定该函数是否是关联的？

类似的问题，但也适用于其他属性，例如交换性。

如果这是不可能的，有没有办法用任何语言自动化它？如果有我感兴趣的 Agda、Coq 或 Prolog 解决方案。

我可以设想一个蛮力解决方案，它检查每个可能的参数组合并且永不终止。但是在这种情况下，“永不终止”是一个不受欢迎的属性。