停止使用非图灵完整的语言 [英] Halting in non-Turing-complete languages

问题描述

图灵完整的语言无法解决停止问题，对于某些非TC语言(例如正则表达式)，它总是可以停止，因此可以轻松解决.

我想知道是否有任何语言既具有停止能力又不具有停止能力，但接受一种可以确定其是否停止的算法.

解决方案

是.这种重要的类之一是原始递归函数.此类包括您希望能够与数字进行的所有基本操作(加法，乘法等)，以及@adrian提到的一些复杂类(正则表达式/有限自动机，无上下文语法/下推式)自动机).但是，确实存在一些不是原始递归的函数，例如 Ackermann函数.

理解原始递归函数实际上非常容易.它们是您可以在没有真正递归的编程语言中获得的功能(因此，函数f不能调用自身，无论是直接调用还是通过调用另一个函数g然后调用f等)，并且没有while循环，而是有界循环.有界的for循环类似于"for i from 1 to r"，其中r是已经在程序中较早计算出的变量.另外，我不能在for循环内进行修改.这种编程语言的要点是每个程序都将停止.

我们编写的大多数程序实际上都是原始的递归程序(我的意思是，可以将其翻译成这种语言).

The halting problem cannot be solved for Turing complete languages and it can be solved trivially for some non-TC languages like regexes where it always halts.

I was wondering if there are any languages that has both the ability to halt and not halt but admits an algorithm that can determine whether it halts.

解决方案

Yes. One important class of this kind are primitive recursive functions. This class includes all of the basic things you expect to be able to do with numbers (addition, multiplication, etc.), as well as some complex classes like @adrian has mentioned (regular expressions/finite automata, context-free grammars/pushdown automata). There do, however, exist functions that are not primitive recursive, such as the Ackermann function.

It's actually pretty easy to understand primitive recursive functions. They're the functions that you could get in a programming language that had no true recursion (so a function f cannot call itself, whether directly or by calling another function g that then calls f, etc.) and has no while-loops, instead having bounded for-loops. A bounded for-loop is one like "for i from 1 to r" where r is a variable that has already been computed earlier in the program; also, i cannot be modified within the for-loop. The point of such a programming language is that every program halts.

Most programs we write are actually primitive recursive (I mean, can be translated into such a language).

这篇关于停止使用非图灵完整的语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！