computation-theory - Starlark转身完成了吗？

Question

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

问题：

• 缺少用户定义的数据类型、无限循环和递归是否足以使语言成为图灵不完整的。

• 有没有证据表明 StarLark 不是图灵完备的？
• 如果一种语言未完成，这是否意味着程序最终会停止？

Answer 1

1. 图灵机程序（或图灵完备语言中的任何程序）可能永远不会因陷入有效的无限循环而停止。排除非终止图灵机程序是不可能的（请参阅停机问题）。因此，任何试图确保所有程序终止的语言（例如 Starlark）都必须牺牲图灵完整性。另请参阅总函数式编程。

2. 看上面。

3. 不必要。在不缺少无限循环的情况下，语言可以通过其他方式实现图灵不完备。例如，唯一允许的程序while True: pass不是图灵完备的语言，但它也不会终止。