turing-complete - 元组关系演算

Question

安全元组关系演算是图灵完备的语言吗？

Answer 1

让我们忘记安全。来自 Codd's theorem ，关系演算等价于一阶逻辑。 FOL 是非常有限的，它不能表达在某个图中有从 A 点到 B 点的路径(它可以表达从 A 点到 B 点的路径的长度有限，例如 ∃ x ∃y ∃z ∃t route(a,x) and route(x,y) and route(y,z) and route(z,t) and route(t,b) 表示存在长度为 4 的路径。

见 descriptive complexity用于描述不同逻辑的强度。