this post was submitted on 27 May 2025
656 points (99.4% liked)
Programmer Humor
23530 readers
1714 users here now
Welcome to Programmer Humor!
This is a place where you can post jokes, memes, humor, etc. related to programming!
For sharing awful code theres also Programming Horror.
Rules
- Keep content in english
- No advertisements
- Posts must be related to programming or programmer topics
founded 2 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Pure SQL, as in relational algebra, is LOGSPACE/PTIME. Datalog is PTIME-complete when the program ("query") is fixed, EXPTIME-hard otherwise.
It's all quite tractable, but there's definitely turing-complete declerative langugages. Not just pretty much every functional language, but also the likes of prolog.