Interesting! Sounds somewhat like what the Cairo programming language & VM does https://www.cairo-lang.org; Turing-complete provable computation using a fairly funky "arithmetic" CPU architecture.
It's possible to build more standard CPUs as well which use ordinary arithmetic, logic and memory, at some cost to efficiency. But the cost is almost entirely borne by the prover.