Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 358 / 1 / b

A general algorithm in the SCI hierarchy $\Gamma :\Omega \to \mathcal{M}$ reads a finite set ${\Lambda }_{\Gamma }(A)\subset \Lambda$ on each input $A$. Its output depends only on those values, and whenever another input $B$ has the same values on ${\Lambda }_{\Gamma }(A)$, the algorithm requests the same finite set and gives the same output. A tower of algorithms of height $k$ satisfiesfor every $A\in \Omega$. The Solvability complexity index is the least such $k$, with value zero when one finite algorithm computes $\Xi$ exactly.

We reduce a known height-three finite-column decision problem to spectral computation. Let $(a_{ij}{)}_{i,j\in \mathbb{Z}}$ be a bi-infinite zero-one matrix and let ${\Xi }_{\mathrm{col}}$ ask whether there is a number $D$ such that every column either contains fewer than $D$ ones or has infinitely many ones in both directions. The lecture lower-bound theorem stateseven for unrestricted general algorithms.

For a zero-one sequence $a=(a_i{)}_{i\in \mathbb{Z}}$, define $B_a$ on ${\ell }^2(\mathbb{Z})$ to be the identity on coordinates where $a_i=0$ and the shift from each coordinate with $a_i=1$ to the next coordinate carrying a one. It is a direct sum of identity pieces and one shift chain. Consequently:

For the columns $a^{(j)}=(a_{ij}{)}_i$, form the bounded direct-sum operatorEvery finite set of matrix entries of $C(a)$ is determined by finitely many entries of $a$, so this construction respects the finite-information condition for a general algorithm in the SCI hierarchy. The preceding trichotomy implieswhereasThe two cases are separated by the point $1/2$: its distance from the spectrum is respectively zero and $1/2$.

If a height-two tower ${\Gamma }_{n_2,n_1}$ computed the spectrum of every bounded operator, apply it to $C(a)$ and inspectUse the disjoint intervals $[0,1/8]$ and $[3/8,\infty )$ to turn each finite output into Yes or No, retaining the latest inner-stage value that lies in either interval. Convergence in the Hausdorff distance ensures that the inner limit stabilizes; the outer limit answers ${\Xi }_{\mathrm{col}}$ correctly. This would give a height-two tower for a problem whose Solvability complexity index is three, a contradiction. Therefore