非图灵完备语言中的停止
对于图灵完备语言来说，停止问题无法解决，而对于某些非 TC 语言（例如总是停止的正则表达式）来说，可以轻松解决。
我想知道是否有任何语言既具有停止和不停止的能力，但又承认一种可以确定是否停止的算法。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
停止问题不适用于语言。 相反，它作用于机器
（即程序）：它询问给定程序是否在给定输入上停止。
也许你想问其他型号是否可以解决这个问题
计算（就像你提到的正则表达式，但也喜欢
下推自动机）。
一般来说，可以在资源有限的模型中检测到停止（例如
正则表达式或等效的有限自动机，它有一个固定的
状态数且无外部存储）。 这很容易通过以下方式完成
枚举所有可能的配置并检查机器是否进入
相同的配置两次（表示无限循环）； 与有限的
资源，我们可以为我们必须看到的时间设置一个上限
如果机器不停止则重复配置。
通常，具有无限资源的模型（例如无限的 TM 和 PDA），
无法停止检查，但最好调查模型并
他们各自的开放问题。
（抱歉所有维基百科链接，但它实际上是一个非常好的资源
这种问题。）
The halting problem does not act on languages. Rather, it acts on machines
(i.e., programs): it asks whether a given program halts on a given input.
Perhaps you meant to ask whether it can be solved for other models of
computation (like regular expressions, which you mention, but also like
push-down automata).
Halting can, in general, be detected in models with finite resources (like
regular expressions or, equivalently, finite automata, which have a fixed
number of states and no external storage). This is easily accomplished by
enumerating all possible configurations and checking whether the machine enters
the same configuration twice (indicating an infinite loop); with finite
resources, we can put an upper bound on the amount of time before we must see
a repeated configuration if the machine does not halt.
Usually, models with infinite resources (unbounded TMs and PDAs, for instance),
cannot be halt-checked, but it would be best to investigate the models and
their open problems individually.
(Sorry for all the Wikipedia links, but it actually is a very good resource for
this kind of question.)
是的。 此类的一个重要类是原始递归函数。 此类包括您期望能够对数字执行的所有基本操作（加法、乘法等），以及一些复杂的类，如 @adrian 提到的（正则表达式/有限自动机、上下文无关语法/下推）自动机）。 然而，确实存在非原始递归的函数，例如 Ackermann 函数。
实际上，理解原始递归函数非常容易。 它们是您可以在没有真正递归的编程语言中获得的函数（因此函数 f 无法调用自身，无论是直接调用还是通过调用另一个函数 g 然后调用 f 等）并且没有 while 循环，而不是有界 for 循环。 有界 for 循环类似于“for i from 1 to r”，其中 r 是程序中先前已计算过的变量； 另外，i 不能在 for 循环内修改。 这种编程语言的要点是每个程序都会停止。
我们编写的大多数程序实际上都是原始递归的（我的意思是，可以翻译成这样的语言）。
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).
简短的回答是肯定的，而且这样的语言甚至可能非常有用。
几个月前，LtU 上曾对此进行过讨论：
http://lambda-the-ultimate.org/node/2846
The short answer is yes, and such languages can even be extremely useful.
There was a discussion about it a few months ago on LtU:
http://lambda-the-ultimate.org/node/2846