undefined | Better HN

0 pointslidHanteyk5y ago0 comments

Complexity theorist here. In addition to your point, there's another commonly-overlooked problem: 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].

It seems like folks are very quick to confuse the expressiveness of a machine with the expressiveness of analyzing programs for that machine; usually, a program is far harder to analyze than to run.

I think that a better way to view the post's author's point is by unpredictability. Given a short program in a weak setting, we can not only predict what the program will do, but what the program cannot do, usually because it is too short or too simple. In a Turing-complete setting, though, there are short programs with very unpredictable behavior.

[0] https://en.wikipedia.org/wiki/Turing_degree

0 comments

fnrslvr5y ago

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.

lidHanteykOP5y ago

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

j / k navigate · click thread line to collapse