Starlark 图灵完整了吗？

Question

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

问题：

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

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

Answer 1

1. 图灵机程序（或图灵完备语言中的任何程序）可能永远不会因陷入实际上的无限循环而停止。排除非终止图灵机程序是不可能的（参见

   停止问题）。因此，任何试图确保所有程序终止的语言（例如 Starlark）都必须牺牲图灵完备性。另请参阅完全函数式编程。

2. 见上文。

3. 不一定。一种语言在不缺乏无限循环的情况下还可以通过其他方式实现图灵不完备。例如，唯一允许的程序是

   while True: pass

    的语言不是图灵完备的，但它也不会终止。