## 3 Quantum Computable Functions
### Computed Output  
We can now come back to the definition of the computed output of a QTM computation. The easy case is when a computation reaches a final q-configuration \(|\psi\rangle\in\mathfrak{C}^{fin}\) (meaning that all of the classical computations in superposition are \"terminated\")--in this case the computed output is the PD \(\mathbf{P}_{|\psi\rangle}\). The QTM keeps computing and transforming \(|\psi\rangle\) into other configurations, but all of these configurations have the same PD. However, we want to give meaning also to infinite\" computations, which never reach a final q-configuration, yet producing some final configurations in the superpositions. For this purpose, we define the computed output as the limit of the PPDs yielded by the computation.  
**Definition 14** (computed output of a QTM).: _Let \(K_{|\phi\rangle}^{M}=\{|\phi_{i}\rangle\}_{i\in\mathbb{N}}\) be the computation of the QTM \(M\) on the initial \(q\)-configuration \(|\phi\rangle\). The computed output of \(M\) on the initial \(q\)-configuration \(|\phi\rangle\) is the PPD \(\mathbf{P}=\lim_{i\to\infty}\mathbf{P}_{|\phi_{i}\rangle}\), which we shall also denote by \(\lim K_{|\phi\rangle}^{M}\), or by the notation \(M_{|\phi\rangle}\to\mathbf{P}\)._  
Let us remark that, by Proposition 1 and Theorem 3, the limit in the above definition is well-defined for any computation. Therefore, a QTM has a computed output for any initial q-configuration \(|\phi\rangle\).  
**Definition 15** (finitary computations).: _Given a QTM \(M\), a q-configuration \(|\phi\rangle\) is finite if it is an element of \(\mathsf{span}(\mathsf{CB}(\mathfrak{C}_{M}))\). A computation \(K^{M}_{|\phi\rangle}=\{|\phi_{i}\rangle\}_{i\in\mathbb{N}}\) is finitary with computed output \(\mathbf{P}\) if there exists a \(k\) s.t. \(|\phi_{k}\rangle\) is final and \(\mathbf{P}_{|\phi_{k}\rangle}=\mathbf{P}\)._  
**Proposition 3**.: _Let \(K^{M}_{|\phi\rangle}=\{|\phi_{i}\rangle\}_{i\in\mathbb{N}}\) be a finitary computation with computed output \(\mathbf{P}\), which is, \(M_{|\phi\rangle}\rightarrow\mathbf{P}\)._  
1. _There exists a_ \(k\)_, such that, for each_ \(j\geq k\)_,_ \(|\phi_{j}\rangle\) _is final and_ \(\mathbf{P}_{|\phi_{j}\rangle}=\mathbf{P}\)_._
2. \(\mathbf{P}\) _is a PD._  
Proof.: By definition, there is a \(k\) s.t. \(|\phi_{k}\rangle\) is final. Let \(\mathbf{P}_{|\phi_{k}\rangle}=\mathbf{P}\). By Proposition 2, \(\mathbf{P}\) is a PD. By monotonicity, \(\mathbf{P}\leq\mathbf{P}_{|\phi_{j}\rangle}\), for every \(j\geq k\). Thus, because any PD is maximal for \(\leq\) (see Remark 6), \(\mathbf{P}=\mathbf{P}_{|\phi_{j}\rangle}\), for every \(j\geq k\).  
Given a computation \(K^{M}_{|\phi\rangle}\), we can then distinguish the following cases:  
1. \(K^{M}_{|\phi\rangle}\) is finitary. In this case, \(M_{|\phi\rangle}\rightarrow\mathbf{P}\in\mathbb{P}_{1}\); the output of the computation is then a PD and is determined after a finite number of steps;
2. \(K^{M}_{|\phi\rangle}\) is not finitary, but \(M_{|\phi\rangle}\rightarrow\mathbf{P}\in\mathbb{P}_{1}\). The output is a PD and is determined as a limit; and,
3. \(K^{M}_{|\phi\rangle}\) is not finitary, and \(M_{|\phi\rangle}\rightarrow\mathbf{P}\in\mathbb{P}\setminus\mathbb{P}_{1}\) (the sum of the probabilities of observing natural numbers is \(p<1\)). Not only the result is determined as a limit, but we cannot extract a PD from the output.  
The first two cases above give rise to what Definition 16 calls a q-total function. However, observe that, for an external observer, cases (2) and (3) are in general indistinguishable, since, at any finite stage of the computation, we may only observe a finite part of the computed output.  
For some examples of QTMs and their computed output, see Section 5.