我用MATLAB脚本语言写了一个简单的Brainfuck解释器,它可以执行随机bf程序(作为基因算法项目的一部分)。 我面临的问题是,在相当多的情况下,程序会出现无限循环,因此GA在那一点上被卡住了。 因此,我需要一种机制来检测无限循环并避免执行bf中的代码。 一个显而易见(琐碎)的情况是当我...
每当人们谈到与编程有关的停机问题时,人们会回答说:“如果你只添加一个循环,你就得到了停机程序,因此你无法自动化任务。” 这是有道理的。如果你的程序有一个无限循环,那么当你的程序运行时,你无法知道程序是仍在处理输入,还是只是无限循环。 但有些东西似乎是违反直觉的。如果我正在编写一个停机问题求...
在工作中你曾经遇到过停机问题吗?这可能是当你的同事/老板提出了一种违反计算基本限制的解决方案,或者当你自己意识到你试图解决的问题实际上是无法解决的时候。 我最近遇到的一个例子是在学习类型检查器时。我们班意识到,要编写一个完美的类型检查器(接受所有不会发生类型错误的程序,并拒绝所有会发生类型错...
几乎所有使用的编程语言都是图灵完备的,尽管这使得该语言能够表示任何可计算算法,但它也带来了自己的一套问题。考虑到我编写的所有算法都旨在停止,我希望能够用一种保证它们会停止的语言来表示它们。 在词法分析时,用于匹配字符串的正则表达式和有限状态机被使用,但我想知道是否有更通用、广泛的语言,而不是...
我刚读了一个关于模拟器的高票问题,其中有这样一句话: 已经被证明,找到给定二进制文件中所有代码与判断一段程序是否能终止的问题是等价的。 这句话真的让我印象深刻。 这难道是真的吗?难道它不只是一个大的依赖图吗? 非常感谢对此声明提供更多深入见解。
是否可能构建一个高阶函数isAssociative,该函数接受另一个具有两个参数的函数,并确定该函数是否是结合性的? 类似的问题也可以用于其他属性,例如交换律。 如果这是不可能的,是否有任何一种语言可以自动化实现?如果有Agda,Coq或Prolog解决方案,我很感兴趣。 我可以设想一种...
看下面这个Java中的无限while循环。它会导致紧接着它下面的语句在编译时出现错误。while(true) { System.out.println("inside while"); } System.out.println("while terminated"); //Unrea...
由于对于每个 f,都有 Nothing >>= f = Nothing,因此以下简单的定义适用于 mfix: mfix _ = Nothing 但这没有实际用途,因此我们有以下非全面的定义: mfix f = let a = f (unJust a) in a where ...
众所周知,停机问题无法有明确的解决方案,即a) 返回true 程序确实停机,b) 处理任何输入,但我想知道是否有足够好的解决方案来解决该问题,可以完美处理某些程序流程,或者能够识别出它不能正确解决问题的情况,或者在大多数情况下是正确的等等... 如果有,它们有多好,并且它们依赖于什么思想...