问题标签 [halting-problem]

当我在这里谈论停止问题时，听起来不终止是要避免的事情，并且停止问题使得无法知道程序/算法是否良好。

但是当我想到它时，终止程序不是例外而不是规则吗？我可以想到一类预计会在有限时间内终止的应用程序：编译器。其他一切，从我正在使用的网络浏览器，到桌面环境，到文本编辑器，到外壳，再到托管 SO 的服务器，再到操作系统本身，都不应该自行终止。哎呀，即使是包管理器也应该要求用户确认。除非用户或系统管理员另有说明，否则它们都打算无限期地运行。

我的观点是，它真的很糟糕，以至于你无法证明某事会终止吗？如果有的话，证明某些东西会在有限的时间内退出将更像是一个错误而不是相反。

我遇到了一个问题，希望对解决方案有一些指导。

我需要证明下一个问题是不可判定的：
输入- 程序
问题- 程序停止的可能输入的数量是否大于程序不会停止的输入数量？

我试图建立一个减少（如果输入是偶数）对每个偶数停止，对每个奇数进入一个无限循环并使用输入运行程序。或者如果输入是奇数，则相反 - 但只有当我能够证明实奇数的数量等于实偶数时它才有效。

由于Nothing >>= f = Nothing对于 every f，以下简单定义适用于mfix：

但这没有实际用途，因此我们有以下非全定义：

如果这个- 子句不会停止，如果mfix f返回就好了。（例如，） 这是不可能的，因为停机问题是无法解决的吗？Nothingletf = Just . (1+)

我正在尝试用我的代码找到由两个 3 位数字的乘积构成的最大回文数。它适用于 2 位数和 3 位数，但是当我尝试使用 4 位数时，它不再起作用了。最后没有输出或“进程以退出代码0完成”。它就像在无限循环中一样停止了。

我哪里做错了？我大约一个月前才开始使用Python，所以我的代码仍然无效

有点愚蠢的问题，但我找不到任何答案。
可悲的是，我犯了一个非常可耻的错误，我不小心创建了一个无限循环。

因为我想强制用户只输入 4 位数字，显然没有意识到我做了一个无限循环MsgBox， 因为一旦你到达>4字符就不可能关闭它，MsgBox即使在你 QueryClose/OK 弹出的那个之后它也会继续创建新的 es .

有没有办法可以取消它，而无需完全关闭 Excel？可悲的是，我什至无法暂停MsgBox以模式形式打开的代码，也无法单击任何编辑器元素。

目前，我们在 AWS EC2 实例上的系统（客户端）在尝试将大文件发送到客户远程 sftp 服务器（“160.xxx.xxx.35.bc.googleusercontent.com）时遇到了 sftp 问题。对于小文件，sftp 传输工作正常，但是当文件大小大约或大于 1GB 时，我们发现只有 1068392448 字节传输到服务器 sftp 站点。但是，当我们将具有相同代码和相同环境的相同大文件发送到我们自己的非 googleusercontent 远程 sftp 服务器（只有 URL/用户名/密码不同）时，它是成功的，并且所有数据都正确传输。

这个问题是在客户服务器端通过添加负载均衡器进程进行一些更改后发生的。客户服务器端进行了一些调查，调整了负载均衡器超时，但无助于解决此问题。据说客户端在 1068392448 字节后停止数据传输，服务器端在允许的空闲时间（~50 秒）后等待并断开连接。

我们的调查注意到大源文件是从 AWS S3 读取并正确保存到本地的。当大文件数据写入服务器 sftp 站点达到1068392448 字节（所有测试结果一致）时，在服务器允许空闲时间（约 50 秒）后，TCP 套接字连接状态从 ESTABLISHED 变为 CLOSE_WAIT。该进程永远保持这种状态，直到它被手动停止/杀死。当 TCP 套接字连接处于 CLOSE_WAIT 状态时，dump 中显示的数据传输过程在 awaitSpace() 方法（在 java.io 包的 PipedInputStream 类中）处于等待循环中。缓冲区被指示为已满并等待写入服务器端。下面是等待循环的代码：

下面是转储：

目前，我们正在使用 com.github 的 vfs-s3 版本 2.4.2 和相关的 apache.commons vfs2 版本 2.1。和 com.jcraft 的 jsch 版本 0.1.54 用于 sftp 数据传输。我们的基本代码如下：

我们尝试在本地 Window 环境中测试相同的代码。有时我们会看到与 ec2 实例中相同的问题症状，但大多数时候问题不存在（不一致）。我们在其他 linux 系统上测试，将大文件发送到客户服务器 sftp 站点，没有问题。

我们尝试在 AWS EC2 实例上升级到 com.github.abashev 的 vfs-s3 版本 3.0.0 和 4.0.0 以及相应版本的 vfs2。但是，它为相同的大文件重现了相同的问题结果。尝试使用正确的配置文件值将 loadOpenSSHConfig 设置为 true 以保持连接处于活动状态，但这对这种情况没有帮助。

我们尝试通过 sftp "put" 命令直接测试 sftp，将大文件从 EC2 实例（和其他 Windows/Linux 平台）发送到远程服务器，并且大文件数据传输始终成功。

问题是问题的潜在根本原因在哪里？为什么服务器端在 1068392448 字节后停止接收数据，或者为什么其余数据无法发送到服务器端？我们的 EC2 环境有任何硬性限制阻止了数据传输操作（我们尝试检查一些限制但仍不清楚）？或者服务器站点错误地向客户端站点发送了连接关闭“FIN”请求（如何证明）？感谢您对潜在解决方案的任何建议。

这是我在阅读停止问题、科拉茨猜想和科尔莫哥洛夫复杂性时突然想到的一个问题。我试图搜索类似的东西，但我无法找到一个特定的主题，可能是因为它没有太大的价值，或者它可能只是一个微不足道的问题。

为简单起见，我将给出三个程序/功能示例。

所以我的问题是，如果有一种方法可以形式化程序的长度（如用于描述它的位）以及程序使用的内部存储器，以确定决定所需的最小/最大时间/步数程序是终止还是永远运行。

例如，在第一个函数中，程序不会改变其内部存储器并在一些时间步后停止。
在第二个示例中，程序永远运行，但程序也不会改变其内部存储器。例如，如果我们考虑与程序 2 具有相同长度且不改变其状态的所有程序，我们是否不能确定步数的上限，如果超过该上限，我们可以得出结论，该程序永远不会终止？（如果不是为什么？）
在最后一个例子中，程序改变了它的状态（变量 i）。因此，在每一步，上限都可能发生变化。

[简而言之] Kolmogorov 复杂性提出了一种查找对象（例如一段文本）的（描述性）复杂性的方法。我想知道，给定描述程序使用的内存空间的正式方式（在运行时计算），我们是否可以计算最大步数，如果超过，我们可以知道该程序是否会终止或永远奔跑。

最后，我想向我推荐任何我认为有用的资源，并帮助我弄清楚我到底在寻找什么。
谢谢你。（对不起我的英语，不是我的母语。我希望我很清楚）

我写了一个非常简单的实现，可能类似于汇编/机器代码。

它甚至可以递归，如下例所示：

输出：720（6的因数）

描述：

-编辑：程序命令： MOV, ADD, SUB, MUL, DIV, MOD, IFEQ, IFNEQ, IFG, IFGE, IFL, IFLE, ENDIF, CALL, RET

但是程序可以进入无限循环/递归。例如：

如何验证我的程序是否会进入无限循环/递归？

这是我的实现，不知道是否有必要，但以防万一。（这是整个代码......希望你不介意）。

我正在使用从 Builtroot 构建的图像，并使用 QEMU 运行。但是当我运行“poweroff”命令时，机器没有关机。并出现“系统停止”！（见下面的控制台输出）

有人能帮我吗？谢谢！

我猜想每个 np-complete 问题都归结为 np-hard 问题，所以给定的陈述是正确的。但不知道如何证明。