Hacker News Reader

Comment by ryangs | Hacker News Reader

I think there is a fundamental gap between the OP's concept of "Point" versus the responders. They're essentially asking if decidability has practical[1] uses to which the answer is generally "No". When a general CS practitioner imagines doing something via computation, they are already thinking of things in the realm of the possible. It may be helpful to know that exact answers are intractable and you'll have to settle for an approximation, but that information seems to correlate more with complexity than with decidability.

[1]: Where practical is in the sense of an engineer (or in their terms, a CS practitioner), not a theoretician. Most of the responders seem to interpret practical in the sense of a mathematician.

View on HN

Decidability has very practical applications. There have been a number of security exploits that have depended on the attacker being able to run a weird machine inside a decoder of some kind, like NSO's iPhone hack:

https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i...

"JBIG2 doesn't have scripting capabilities, but when combined with a vulnerability, it does have the ability to emulate circuits of arbitrary logic gates operating on arbitrary memory. So why not just use that to build your own computer architecture and script that!? That's exactly what this exploit does. Using over 70,000 segment commands defining logical bit operations, they define a small computer architecture with features such as registers and a full 64-bit adder and comparator which they use to search memory and perform arithmetic operations. It's not as fast as Javascript, but it's fundamentally computationally equivalent.

The bootstrapping operations for the sandbox escape exploit are written to run on this logic circuit and the whole thing runs in this weird, emulated environment created out of a single decompression pass through a JBIG2 stream. It's pretty incredible, and at the same time, pretty terrifying."

They're essentially asking if decidability has practical[1] uses to which the answer is generally "No".

I don’t think I agree! For example, I strongly suspect that Malware detection researchers would be following many fruitless paths in the vein of “Let’s just figure out what the program is doing” if not guided by the fact that this is strictly harder than “Let’s just figure out if the program halts.”

> Where practical is in the sense of an engineer (or in their terms, a CS practitioner),

Configuration processing. E.g. I'd like my yamls to be decidable, though I'll settle for guaranteed to halt[1].

[1] https://dhall-lang.org/

> they are already thinking of things in the realm of the possible.

very astute observation. Now I'm left wondering how this comes to be?

what is it about the way in which a general CS practitioner's approach to problem solving that grounds the potential ideas (of how to solve problem) into the computationally decidable?

Reply on news.ycombinator.com