Can Zk-SNARKs verify the results of turing-complete computations?
Yes. Express $f$ as a (say, Boolean) circuit. If $f$ is poly-time it will have a number of gates that is polynomial in the input size. A universal circuit $U$ is a Boolean circuit that evaluates any circuit up to bounded size (see e.g. this eprint from 2017 by Günther, Kiss and Schneider). The input to $U$ will be bits representing the structure of the circuit of $f$. Since $U$ is just another Boolean circuit, it can also be represented as a QAP as in the Pinocchio paper, or whatever the zk-SNARK uses.