Hacker News new | ask | show | jobs
by maweki 515 days ago
There are many useful things that are not turing complete and still considered programming.

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.

1 comments

I don't have any problems with calling it programming even if it's not Turing complete. But I think it's nice to clarify, so I can understand where it is in the expressivity-landscape.

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.