A guarantee of completion isn't strictly necessary: you can cap the number of ticks/cycles a script is allocated on a deterministic reference machine.

Surely there'd be a number of technical and economic challenges to be overcome, but Bitcoin itself is an example of how a good-enough solution may be hiding in plain sight.