According to https://news.ycombinator.com/item?id=18496054, these programs have to halt? How does this system guarantee that the programs halt? Does this mean eBPF is not Turing complete?
There are three categories of programs; programs you can trivially prove will halt, programs you can trivially prove won't halt, and programs where it's difficult or impossible to prove whether or not will halt. The third category is what we call the halting problem. Only the first category will be run by the kernel.
The nitty gritty is that the only jumps which are allowed to go backwards are the end of a loop with a fixed number of iterations. All other jumps must jump forward.
This sounds like it's really limiting, but in practice there's not a whole lot of useful stuff you're unable to do.
With a fixed number iterations (which also means fixed amount of memory) it's really just a finite state automata.
https://en.m.wikipedia.org/wiki/Total_functional_programming
In practice that means a true Turning machine can compute things that aren't actually computable in our Universe, or at least not by the bits of the Universe we understand well. I doubt any engineer will think that "this architecture can't in theory compute things not computable in this Universe" is a strong argument against it.