The way to solve this is static analysis. I'm not giving up on the Turing machine, so we'll just need a way to analyze a given machine to determine whether it falls in to your low power use case.