斯塔尔百灵完成了吗？

Question

星云雀配置语言不支持无限循环、递归或用户定义的数据类型，但它确实支持函数。文档表明，这意味着语言不是图灵完整的。我忘记了很多关于语言和自动机理论的计算机科学课程。

问题：

• 缺少用户定义的数据类型、无限循环和递归，足以使一种语言变得不完整。
• 有证据证明StarLark不是图灵完整的吗？
• 如果一种语言不完整，这是否意味着程序最终会停止呢？

Answer 1

1. 图灵机程序(或图灵完整语言中的任何程序)可能永远不会陷入实际上是无限循环的状态。排除不终止图灵机程序是不可能的(参见停止问题)。因此，任何试图确保所有程序终止的语言(如Starlark)都必须牺牲图灵的完整性。另见全功能程序设计。
2. 请参见上面的。
3. 不一定。有其他方法，一种语言可以图灵不完整，而不缺乏无限循环。例如，一种语言，其中唯一允许的程序是while True: pass不是图灵完成，但它也不终止。