turing-complete - タプル関係計算

Question

安全なタプル関係計算はチューリング完全言語ですか?

Answer 1

安全のことは忘れましょう。コッドの定理により、関係計算は一階論理に相当します。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 のルートがあることを意味します)。

さまざまなロジックの強みの説明については、記述の複雑さを参照してください。

Answer 2

コッドの定理によれば、関係代数と関係微積分は同等です。関係代数がチューリング完全ではないことはよく知られているため、関係計算もそうではありません。

[編集]たとえば、集計操作 (合計、最大など) を実行したり、関係代数/微積分で再帰クエリを作成したりすることはできません。こちらをご覧ください（終盤）。