How Vector Addition Keeps Your Computer from Crashing: The Reachability Problem

How can a programmer ensure a critical piece of software is bug-free? Theoretical computer scientists use a fundamental question called the reachability problem, which determines whether a computer will reach or avoid various dangerous states when running a program. To better understand the complexity of the problem, researchers turned to a mathematical tool called vector addition systems. In a series of recent breakthroughs, computer scientists have now determined that the complexity of the reachability problem for vector addition systems is defined by a famous function called the Ackermann function, which becomes extremely complex even with small inputs.
----------

CORRECTION: March 13, 2024
Around the same time as Czerwiński and Orlikowski's 2021 paper that raised the lower bound to Leroux and Schmitz’s Ackermann upper bound, Leroux obtained an equivalent result, working independently. Both papers proved the same lower bound and the teams coordinated to publish the papers at the same time. Links to their work can be found here:

----------
Chapters:
00:00 How formal verification finds programming bugs
00:59 The Reachability Problem
01:41 Origins of concurrent computing and resultant challenges
02:40 Vector addition systems (vass) and the reachability problem
04:16 Searching for the complexity of the problem, what's the fastest algorithm?
04:38 Identification of lower and upper bounds of the reachability problem
06:18 The Ackermann function explained
07:32 A final solution to the vasa reachability problem is found

----------

[QuantaScienceChannel]

CORRECTION: March 13, 2024
Around the same time as Czerwiński and Orlikowski's 2021 paper that raised the lower bound to Leroux and Schmitz’s Ackermann upper bound, Leroux obtained an equivalent result, working independently. Both papers proved the same lower bound and the teams coordinated to publish the papers at the same time. Links to their work can be found here:

[Winium]

Note: Ackermann function is often presented as A(m, n), i.e. it has two parameters. What's presented in the video is the "diagonalized" single-param version. Actually, there are "many" Ackermann functions, and the original had three arguments: A(m, n, p) = the "p-th" hyperoperation on m and n. A(2, 3, 0) = 2 + 3. A(2, 3, 2) = 2^3, etc. The single param version in the video seems to use m = n = p.

[teeesen]

The video glosses over just how difficult Lipton found the problem to be in 1976. His paper 4:40 showed that the VAS reachability problem requires exponential space. This already means that any perfect algorithm for it will be highly impractical. For people interested in solving other problems —like problems in program verification— it means that reducing their problems to VAS reachability is not all that useful. We knew it was at least bad; now we know it’s worse than bad.

[Scriabin_fan]

It blows my mind that there are people out there that are intelligent enough to come up with such wonderful abstractions to describe and help solve real physical problems. I would've never been able to see the connection between vector addition and determining the end state of an algorithm. This is blowing my mind because of how much sense it makes.

[jopearson]

Gonna be honest, I disagree with the premise. It sounds extremely unbelievably hard to solve. I mean, maybe I'm biased as a programmer, but I don't know how you could look at this area and think its going to be easy.

[jonwatte]

Formal proofs do help with implementation bugs, but the real big bugs are specification and requirement bugs. If you apply formal proof to those, you just end up with a proof that the program implement the broken requirements, without telling you that they are broken.

[willowZzzzzz]

It's not just a CS issue. If you can't ask a perfect question, you won't get the answer you might expect. That's why disciplined CS design revolves around requirements. The old project management saying of "garbage in = garbage out" applies.

[thumbtack]

FORMAL VERIFICATION MENTIONED 🔥🔥🔥 🗣️💯🗣️ 💯

[aleksszukovskis]

quanta magazine is the most underrated channel imo

[tonelemoan]

5:15 off-topic ( I apologies) but I am amused that the generative AI upscale on the background is having a field day with those book titles on the shelf behind him!

[sharmakefarah]

Note also that if we want to detect bugs in general, it is way harder in the Turing Machine model, as it is at least as hard as the halting problem, if not harder.

[Rudxain]

3:25 For a Fibonacci iterator, the rule would be [x, y]->[y, x+y], and the (typical) initial state is [0, 1]. This basically means that a Fib function is a program with 2 parameters, which can be efficiently predicted using Binet's Formula (for Complex numbers) or the Matrix form (for Integers)

[sharmakefarah]

Note that if we use Turing Machines as the model of programs, rather than the vector addition system, it gets even harder, and is at least as hard as the halting problem for the reachability problem for Turing Machines.

[seasong]

We had to learn some kind of verification like this in college called Hoare logic. I don't think I ever got how it really works

[sdjhgfkshfswdfhskljh]

Astronomical amount of choices, which programming allows to make, is one of the reasons why I like it.
Regular people may think that there is single possible solution for some programming problem, but in fact there are way more options available.

[keyboard_toucher]

5:57 As you said earlier in the video, there was at least one long-known algorithm with a higher complexity than the lower bound, so it seems false that discovering the elevated lower bound "confirmed that the problem was far more complex than anyone had imagined." I'm not familiar with vector addition systems, but I suspect Czerwiński's "surprise" was not because he thought the old lower bound was precise, but simply because it's not every day that he makes such fruitful progress on a longstanding question.

[morryDad]

I remember when a VP put out a call for someone to write a program to do root cause analysis: find why a program failed. I didn’t know about reachability at the time, but I replied, with a very polite answer, saying what he was asking for, was either impossible or incredibly difficult.

[pauljones]

Best channel other than scishow for showing new developments in interesting ways

[JohnBerry-qh]

I wish the video had just said ACKERMAN right from the beginning. When I took Computer Science, we studied the Ackerman function when we studied recursion.

[kdalkafoukis]

From the introduction I thought it was undecidable. Sounds very exciting