实用的非图灵完整语言？

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

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

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

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

1> Mr. Putty..：

---

不要听反对者的意见.如果您想要保证终止或简化代码,例如通过消除运行时错误的可能性,那么在某些情况下,人们可能更喜欢使用非图灵完整语言是有充分理由的.有时,忽略事情可能还不够.

论文总功能编程或多或少有说服力地说,事实上我们几乎总是喜欢这种受限制的语言,因为编译器的保证是如此强大.能够证明程序停止本身就很重要,但实际上这是更简单的语言提供的更容易推理的产物.作为不同能力语言层次结构中的一个组成部分,非通用语言的效用范围非常广泛.

另一个更完整地解决这种分层概念的系统是休谟.在休谟的报告给出了系统的完整描述和其逐步更加完善,并逐步不太安全,语言五层.

最后,不要忘记慈善事业.它有点抽象,但它也是一种非常有趣的方法,可用于有用但不通用的编程语言,它直接基于类别理论的概念.

2> Adam Rosenfi..：

---

BLOOP(简称乙 ounded 环路)是一个有趣的非图灵完备的语言.它本质上是图灵完备语言,有一个(主要)警告:每个循环必须包含迭代次数的界限.不允许无限循环.因此,可以为BlooP程序解决暂停问题.

---

当然假设它们没有未绑定的递归或动态自我评估/执行的能力,两者都是无限的迭代后门.

3> hasen..：

---

问题不在于图灵机,而在于"算法".您无法预测算法是否会停止的原因是:

function confusion()
{
    if( halts( confusion ) )
    {
        while True:
            no-op
    }
    else
        return;
}

任何不能进行递归或循环的语言都不会真正"通用".

正则表达式和有限状态机是一回事!词汇和字符串匹配是一回事!FSM停止的原因是因为它们永远不会循环; 他们只是传递char-by-char输入并退出.

编辑:

对于许多算法,很明显它们是否会停止.

例如:

function nonhalting()
{
    while 1:
        no-op
}

这个功能显然永远不会停止.

而且,这个功能显然会停止:

function simple_halting_function()
{
    return 1;
}

最重要的是:你可以保证你的算法停止,只需设计它就可以了.

如果你不确定算法是否会一直停止; 那么你可能无法用任何保证"停止"的语言来实现它.

---

没有递归或循环的语言对于大多数用途来说不是很有用,但是只有保护递归的语言可以是完全的并且仍然可用于许多目的.

4> physis..：

---

慈善不是图灵完整,它不仅在理论上,教学上有趣(类别理论),而且,它可以解决实际问题(河内塔).它的强度非常大,甚至可以表达阿克曼的功能.

5> grieve..：

---

事实证明,完成图片相当容易.例如,你只需要8个指令ala BrainF**k,更重要的是你真的只需要一条指令.

这些语言的核心是一个循环结构,只要你有无界循环,就会有一个固有的停顿问题.循环何时终止？即使在支持无界循环的非图灵完整语言中,您仍可能在实践中遇到停顿问题.

如果您希望所有程序都终止,那么您只需要仔细编写代码.一种特定的语言可能更符合您的喜好和风格,但我认为任何语言都不能完全保证最终的程序会停止.

---

顺便说一下,有*许多*语言可以保证终止.最合适的一个是LOOP(Meyer&Ritchie,1967; Hofstadter也在'Gödel,Escher,Bach'中描述),它基于*循环......但它们总是有界限的.因此,所有LOOP程序*将最终停止,因此它们的停止问题是可判定的.此外,正如其他答案中所提到的,依赖类型的编程语言通常会限制您编写总函数,这些函数必须按定义终止.