My current "VM" inspirations include...regular expressions, constraint logic, modular synthesizers, three-ring binders.

You can go really, really far away from a computing system being a Turing machine with arithmetic, if you work at it - like, that's the thing you already have in every PL. But I think getting away from that also entails getting down and dirty with your chosen benchmark of expressiveness, and accepting that the system does not do some things well, and if you want to have multiple things coordinated, then you need to be careful about expressing that, too, to avoid just making a Turing tarpit.