标签: halting-problem

已经说明了所有agda程序终止的几个地方.但是我可以构造一个这样的函数:

stall : ? n ? ?
stall 0 = 0
stall x = stall x

语法高亮显示器似乎不喜欢它,但没有编译错误.

计算stall 0结果的正常形式0.计算结果stall 1导致Emacs挂起看起来很像非终止循环.

这是一个错误吗？或者Agda有时会永远运行？或者是更微妙的事情？

检测确定性程序（即状态机）是否处于无限循环相当于解决停机问题吗？

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

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

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

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

对于集合中的不同值,此算法(pseudeocode)是否会终止？

while (curElement != average(allElements))
{
    curElement = average(allElements);
    nextElement();
}

请注意,我假设如果我们在数组的末尾,我们将从头开始重新启动.

有一个工具称FindBugs它可以检测给定程序/代码库中的无限永不停止循环.

这意味着FindBugs可以通过分析代码来检测程序是否结束.暂停问题是定义以下问题:

给定任意计算机程序的描述,确定程序是否完成运行或继续运行

那么这是否意味着停止问题得到解决或停止问题的一部分得到解决？

我正在寻找图灵机暂停问题的简单解释.我知道TM的工作原理,它们如何枚举,机器配置等等,但我没有很好地处理暂停问题.

有人可以提供这个主题的好解释吗？

我正在尝试创建一个函数来识别python文件中的代码是否会通过无限循环.这是我到目前为止:

def reader(filename):
    myfile = open(filename)
    counter = 0 
    #counters the number of lines in the file
    for line in myfile:
        counter +=1
        print line
    #print number of lines in file    
    print counter

    #execute the code in file        
    execution = execfile(filename)

我要做的是执行文件,并尝试计算执行的行数,并将其与前一个计数器中的任何数字进行比较.例如,如果计数器> lines_exected,则返回True,代码中存在无限循环.这会有用吗？或者我还需要尝试别的吗？

我有这个功能:

isUndefined :: () -> Bool    
isUndefined x = case unsafePerformIO $ (try (return $! x) :: IO (Either SomeException ())) of
                    Left _ -> True
                    Right _ -> False

然后:

isUndefined () = False
isUndefined undefined = True

解决停止问题.当然,这也可以扩展到其他类型.

我的问题:这怎么可能？难道Control.Exception.try真的破事吗？

我试图在Python(或伪代码)中找到一个编写高级函数的算法 - 不必停止 - 对于给定的函数列表[f1,...,fn]和给定的函数输入列表[x1,...,xn]仅打印一次fi(xj)(表示所有功能和输入对).

当然,实现这一点的天真建议是:

for f in lst1:
   for x in lst2:
      f(x)

但问题是,某些功能可能会在某些输入上永远循环.

我被允许使用一个步进器(它有一个step()方法,每次调用该函数的一个后续计算步骤)

我只需要一个关于如何做的想法或算法.

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

Private Sub Textbox1_Change()
    Do While Len(Trim(Textbox1.Text)) > 4
       MsgBox "Please enter your birthyear in format of ####"
    Loop
End Sub

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

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

假设存在一个实现停止问题的Haskel函数:

halt :: Integer->Bool

如果定义了x,则求值为True,否则求值为False.

假设我们在Haskell中调用此函数作为另一个函数

fHalt x = halt (x+1)

我想知道在这种情况下会发生什么,以及fHalt是单调的.我可能会得到2个答案:

1. Haskell对预定义的运算符使用严格评估 - 也就是(+).如果现在用BOT评估fHalt,我的猜测是必须首先评估BOT + 1(导致BOT),因此整体评估不会终止并导致BOT.

2. 如果Haskell以某种方式确定内部(x + 1)没有终止(由于停止问题而不可能),结果将是False,而fHalt将违反单调性.

在这一点上,我很生气,因为我的问题已经暗示了Haskell中定义的不可实现的暂停函数.虽然我认为答案1.是正确的.