Surprisingly Turing-Complete

Re:Surprisingly Turing-Complete by fnrslvr on Sunday April 12, 2020 @03:05AM (#22846541)

I don't think this discussion thread is giving the writer's concern enough credit. Universality on its own obviously doesn't allow the instance to take over its host, but it can enable the bulk of the malicious payload to be encoded as legitimate instances of whatever P-hard optimization problem the cloud service solves, so that it need not be injected directly via the actual vulnerability that the malicious actor uses to take over the host.

> TC isn't quite the actual top! There are ways to make problems that, even with an oracle for solving Halting, are still hard [0].

I'm not sure why you're raising the subject of the degrees here. Malicious software doesn't need to have hypercomputational powers to be a threat.

[ Parent | on HN ]

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

[ Parent | on HN ]