So BPF introduced a very limited bytecode, which is complex enough that it can express long filters with lots of and/or/brackets - but which is limited enough it's easy to check the program terminates and is crash-free. It's still quite limited - prior to ~2019, all loops had to be fully unrolled at compile time as the checker didn't support loops.
It turned out that, although limited, this worked pretty well for filtering packets - so later, when people wanted a way to filter all system calls they realised they could extend the battle-tested BPF system.
Nobody is claiming to have solved the halting problem.
