Hm, what would be the advantage of a TM over computing f(x) directly? A TM would let us make f dynamic, but it doesn’t seem like your scheme requires that.
For verification, you’d probably end up with an interactive protocol along the lines of what @clesaege discussed here, right? See also Bunz et al.