[nwallin]

The language itself is Turing complete, but the kernel will refuse to run a program that it cannot prove will halt.

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.

[fireant]

Could you create an unbounded loop by scheduling another BPF execution on the end of each program? I imagine something like a WASM runtime that would be split into multiple BPF programs on loops. Which would practically achieve https://github.com/nebulet/nebulet, right?

[cube2222]

This does actually mean that eBPF is not Turing complete, in that it can't simulate a Turing machine.

With a fixed number iterations (which also means fixed amount of memory) it's really just a finite state automata.