News for hackers. Stuff that matters.
Re:Surprisingly Turing-Complete by lidHanteyk on Sunday April 12, 2020 @12:02PM (#22849073)
I think that, if you're going to care about being exploited by real-world payloads, then Turing-completeness is a red herring; I agree with the thread-starter. For example, it is already bad enough to not be able to tell when computations are in P vs. NP, for responsiveness under load. It is not good when an NP database query halts a P Web server. For this reason, languages like Pola [0] which are far weaker than Turing-completeness are valuable.

And, if you thought that it was easy to be accidentally Turing-complete, wait until you see how easy it is to be accidentally NP [1]. The typical database query is in NP, because constraint satisfaction problems are in NP. So is the typical optimization problem.

[0] https://www.researchgate.net/publication/266217730_Pola_a_la...

[1] https://en.wikipedia.org/wiki/List_of_NP-complete_problems

There are no comments on this comment yet.