From the paper: "often people take “Datalog” to specifically refer to “function- free” logic programs where term constants have no arguments, a condition sufficient to ensure that every program has a finite model. We follow many theoretical developments and practical implementations of datalog in ignoring the function-free requirement." If every program has a finite model, the language cannot be Turing complete: the reverse is not necessarily true but in practice the reverse is usually true.
What is the reverse here? Sorry it's late and I can't calculate it.
Btw, what I know about ASP is that it is incomplete (in the sense of soundness and completeness). Turing completeness is a separate question.
If it is not possible to give every program a finite model, that doesn't imply that language IS Turing complete. However, in practice, a Datalog-family logic programming language where some programs have infinite models is likely, in my experience, to be Turing Complete.
(For what it's worth, I don't know what it means for ASP to be incomplete in the sense of soundness and completeness. Incomplete relative to what other thing?)
Regular Excel formulas are always terminating and therefore not computationally complete.
SQL without recursive CTEs is always terminating and therefore not computationally complete.
Simply typed lambda calculus is always terminating and therefore not computationally complete.
It's not the same, but restriction to terminating subsets gives very nice guarantees for a lot of program properties that would otherwise be undecidable.
Maybe it's obvious for the intended audience, given the mention of Datalog? But I suspect a lot of compsci people know of Prolog, and know about SAT(and similar) solvers, but don't really know how e.g Datalog places.
