Why is this computer science problem so hard to solve?

Researchers use a process called formal verification to ensure critical computer programs are free of bugs. Inside this process is a math problem call the reachability problem for vector addition systems. Find out how this problem was solved by computer scientists.

--------
@QuantaScienceChannel

#math #computerscience #science

[wilville]

Computer sceintists when they get dingle farts algorithm from running to running (it still takes 1200 trillion years to run)

[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.

[Julzaa]

Smart-contract audit firms (in blockchain) usually use formal verification as their number 1 tool! And that has been the case for years, it's a very impressive technology

[kilianlindberg]

I always come to think of my good old analog synthesizer Yamaha CS-15, Cymatics and hmm the idea of Ai models in pre-modeled laser-bouncing crystals reconfigurable via quantum sensor calibrated electromagnetic interference
😁🔮 sometimes it’s nice to see how light bounces on a lakes winter landscape in the wind. We have yet so much to discover of what we take for granted.

[idwtgymn]

The reachability problem was not even close to solved. It is so far from solved this video is essentially a complete falsehood.

[cactustree]

So is Schrodinger's cat really dead?

[HotBlack]

What the fuck? What are you talking about? What paper is this hyping?

[nexovec]

It seems completely obvious that there would be no way to do this. Doesn't even seem like something provable. But maybe, mathematicians do freaky stuff these days.

[GrandTerr]

Impressively stupid question. How can you know without testing? The dumbest thing I've ever heard.