One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc.
Below, we will first define this concept, and then investigate some of its properties:
Let $U=\{U_n\}$ and $V=\{V_n\}$ be two distribution ensembles, indexed by natural numbers. That is, for every $n \in \mathbb{N}$, $U_n$ and $V_n$ are probability distributions. We call $U$ and $V$ computationally indistinguishable if, for all probabilistic Turing machine $D$ which is polynomial-time in the length of its first input, all positive polynomial $p(\cdot)$, every sufficiently large $n \in \mathbb{N}$, and all advice strings $z \in \{0,1\}^*$:
$\left|\Pr_{u \leftarrow U_n}[D(1^n,u,z)=1]-\Pr_{v \leftarrow V_n}[D(1^n,v,z)=1]\right|<\frac{1}{p(n)}.$
The probability is taken over the choice of $u$ and $v$, as well as the internal coin tosses of $D$.
An equivalent definition is obtained by replacing the $\forall z \in \{0,1\}^*$ part by a quantifier over all functions $f$, and letting $z=f(1^n)$. Note that $f$ can be an uncomputable function.
The question is:
Are there distribution ensembles $U$ and $V$ which are computationally distinguishable, but if we restrict $f$ to computable functions, then $U$ and $V$ are computationally indistinguishable?
Goldreich argued that in cryptographic settings, where all parties are modeled by probabilistic polynomial-time Turing machines, $f$ must be computable by a polynomial-time machine.
Now consider other settings, such as the case of single- or multi-prover interactive proofs. It is proven (Shamir, Babai et al.) that the parties in such systems need not be more powerful than PSPACE and NEXP machines, respectively.
Is it rational to consider uncomputable functions $f$ in such cases? In particular, do we need to consider $f$ to be computable by machines whose power is beyond PSPACE or NEXP, respectively?