标签: turing-complete

我读过"什么是图灵完整"和维基百科页面,但我对正式证据不太感兴趣,而不是图灵完全的实际意义.

我实际上要确定的是,我刚刚设计的玩具语言是否可以用作通用语言.我知道我可以证明我是否可以用它来编写图灵机.但是,在我确信成功之前,我不想进行这项运动.

有没有最低限度的功能,没有图灵完整性是不可能的？是否有一系列功能几乎可以保证完整性？

(我的猜测是条件分支和可读/可写的内存存储将使我的大部分方式)

编辑:

我想我已经说过"图灵完成"了.我试图以合理的信心猜测具有特定功能集的新发明的语言(或者具有特定指令集的VM)将能够计算任何值得计算的东西.我知道证明你可以用它建立图灵机是一种方式,但不是唯一的方法.

我所期待的是一套类似的准则:"如果可以做X,Y和Z,它可以或许做任何事情".

最近在工作中,我一直在从Makefile转换到另一种构建系统.我在一些地方看到了一些非常多毛的Make代码,使用了功能映射,过滤器和foreach结构.这让我感到惊讶,因为我认为构建脚本应尽可能具有声明性.

无论如何,这让我想到:是Makefile语言(说最新的GNU make具体)Turing完成了吗？

几乎所有使用的编程语言都是图灵完备,虽然这提供了语言来表示任何可计算的算法,但它也有自己的一组问题.看到我写的所有算法都打算停止,我希望能够用一种语言来代表它们,以保证它们会停止.

正则表达式用于匹配字符串和有限状态机在使用时词法,但我不知道是否有这不是图灵完整更普遍的,广泛的语言吗？

编辑:我应该澄清,通过'通用'我不一定希望能够在语言中编写所有停止算法(我不认为这样的语言会存在)但我怀疑有共同的线程停止可以推广的证明,以产生一种语言,保证所有算法都停止.

还有另一种解决这个问题的方法 - 消除理论上无限记忆的需要.一旦限制了机器允许的内存量,机器所处的状态数是有限且可数的,因此您可以确定算法是否会停止(通过不允许机器进入之前的状态) ).

我一直在阅读各种类型的系统和lambda calculi,我发现lambda立方体中的所有类型的lambda结石都是强烈正常化而不是图灵等效.这包括系统F,简单类型的lambda演算加多态.

这引出了以下问题,我一直无法找到任何可理解的答案:

• (例如)Haskell的形式主义与表面上基于的微积分有何不同？
• Haskell中的哪些语言功能不属于System F形式主义？
• 允许图灵完整计算所需的最小变化是什么？

非常感谢你帮助我理解这一点.

我刚刚尝试创建最小的语言解释器.你想加入并尝试吗？

游戏规则:

• 您应该指定您正在解释的编程语言.如果它是您发明的语言,它应该在评论中附带一个命令列表.
• 您的代码应该从分配给代码和数据变量的示例程序和数据开始.
• 您的代码应以结果的输出结束.每个中间步骤最好有调试语句.
• 您的代码应该像编写的那样运行.
• 您可以假设数据为0和1(int,string或boolean,您的选择)和输出是一位.
• 对于在标准模型上编写的任何算法,例如图灵机,马尔可夫链或您选择的类似算法,语言应该是图灵完备的,如果编写一个程序后,如何编写一个程序是相当明显的(或解释)由您的口译员执行算法.
• 代码的长度定义为删除输入部分,输出部分,调试语句和非必要的空格后代码的长度.请将结果代码及其长度添加到帖子中.
• 您不能使用使编译器为您执行代码的函数,例如eval(),exec()或类似的函数.

这是一个社区维基,这意味着问题和答案都不会从投票中获得声誉点.但无论如何投票!

我的儿子最近一直在玩Little Big Planet 2,我注意到游戏编辑器允许AND门,OR门和NOT门......图灵是否完整？如果是这样,任何人都可以推荐一个学习如何将这些原语转换为更高级别条件的来源吗？

我只是想知道它是否100%可能,如果我的语言是turing-complete,写一个打印出来的程序(当然不使用文件读取功能)

因此,如果语言只有真正必要的东西,以使其完成(我会证明通过将Brainf*ck代码翻译成它),如输出,变量,条件和gotos(地狱是的,得到的),我可以尝试在里面写一个quine？

我也问这个问题,因为我不确定quin是否直接符合图灵定律,即图灵机能够完成任何计算任务.我只是想知道,所以我不会尝试多年而不知道这可能是不可能的.

Scala使用基于SystemFω的类型系统,通常认为它是强正规化的.强烈归一化意味着非图灵完整性.

然而,Scala的类型系统是Turing-complete.

与正式算法和系统相比,哪些更改/添加/修改使Scala的类型系统图灵完整？

我正在听edX课程,教授强调每台能够执行这六个基本原语的机器都可以称为图灵完成.但六个基本原语是什么？

Scala和Haskell拥有"图灵完整型系统".通常,图灵完整性是指计算和语言.它在类型的背景下真正意味着什么？

有人可以举一个程序员如何从中受益的例子吗？

PS我不想比较Haskell和Scala的类型系统.一般来说,这更多的是关于这个术语.

PSS如果有可能更多的Scala示例.