To make things concrete let's look at an example. Computational state in a block chain contract is typically stored in a Merkle hash trie. Let's say that the data stored is a key, and the holder of the key is allowed to spend the coins bound to the contract. The _computation_ is to check that the key is contained within the Merkel trie, then check signature of the key and the spend. However with some cool zero-knowledge crypto magic, you don't even have to reveal the Merkle inclusion proof, nor even the key itself. All you have to do is provide a zero-knowledge transcript which verifies that the computation of the contract (Merkle inclusion proof and signature check) validates. This is, essentially, how zerocash works.
This result generalizes. For whatever computation you want to perform in a contract, the contract can be rewritten to instead just validate a transcript of a successful execution of that computation. This isn't just academic either. All NP problems have transcripts that are validatable in polynomial time. A derivative of this result is that while you might need Turing completeness to express the logic of a smart contract, you do NOT need Turing completeness to validate its transcript. As a trivial example, a smart contract that involves computing a hash preimage by brute force in a tight loop, could be replaced with a contract that merely takes a string and checks that it hashes to the desired value.