\subsection{What gradient descent can converge to}\label{subsec:gdlimits}

\Cref{thm:A} is a uniform statement: the limit operator of gradient descent is as hard as $\lm$. Finite path length
has a second, non-uniform consequence, which locates the \emph{values} of this operator precisely. Recall from
\cref{subsec:weihrauch} the left-c.e., right-c.e.\ and d.c.e.\ reals. Ambos-Spies, Weihrauch and Zheng \cite{AmbosSpiesWeihrauchZheng2000WeaklyComputable} showed that the d.c.e.\ reals form a field and are exactly the
limits of computable sequences of rationals with finite total variation; they form a proper subclass of the
limit-computable ($\Delta^0_2$) reals, which are the possible values of $\lm$ on computable inputs.

The following corollary is a direct consequence of known results: part (b) combines self-contraction with the
characterization just quoted, and part (a) is in substance contained in the work of Zheng, Rettinger and Barmpalias
on monotonically computable reals \cite{ZhengRettingerBarmpalias2005hMonotonically} and in Neumann's constructions
\cite[Corollary 3.18]{Neumann2015LMCS}. We state it because it gives a sharp answer to a natural question about
gradient descent that, as far as we know, has not been asked.

\begin{corollary}[The limits of gradient descent]\label{thm:F}
Call an instance $(f,g,L,x_0)$ of \eqref{eq:gd} computable if $f$, $g$ and $x_0$ are computable, $L$ is
rational, and $f$ has a minimizer.
\begin{enumerate}[nosep,label=\textup{(\alph*)}]
  \item In dimension $1$, the limits of gradient descent on computable instances are exactly the reals that are
  left-c.e.\ or right-c.e.
  \item In every dimension $d$, every coordinate of the limit of a computable instance is d.c.e.
  \item In every dimension $d\ge2$, every d.c.e.\ real is the first coordinate of the limit of a computable
  instance.
\end{enumerate}
Every computable instance has a computable minimizer, while the limit may be non-computable.
\end{corollary}

The step size matters in (b): if $L$ is allowed to be a non-computable real, the limit can be far more complex. For
instance, for $f(x)=\frac12((x_1)_+)^2+\frac1{10}((x_1+2x_2)_+)^2$ and $x_0=(1,1)$, every $L$ in $[1+5^{-1/2},8/5]$
is admissible and the limit has first coordinate $\frac25-\frac4{5L}$, which has the Turing degree of $L$.

\begin{proof}
(a) In dimension one $T=I-\frac1Lg$ is nondecreasing, so the iterates are monotone, and a computable monotone
sequence of computable reals has a left-c.e.\ or right-c.e.\ limit. Conversely, let $\alpha$ be left-c.e.\ and
fix rationals $c<\alpha$ and $\lambda>\alpha-c$. Then $\alpha=c+\lambda\sup_sy_s$ for a computable nondecreasing
sequence of rationals $y_s\in[0,1)$. With $f_y$ from \eqref{eq:fy}, the function
$\varphi(u)=\lambda^2f_y((u-c)/\lambda)$ is convex with $2$-Lipschitz derivative, and gradient descent with step
$1/2$ from $u_0=c$ satisfies $u_k=c+\lambda x_k$, where $x_k$ is gradient descent for $f_y$ from $0$. So
$u_k\to c+\lambda\sup_sy_s=\alpha$. Right-c.e.\ reals are handled by $u\mapsto-u$.

(b) By \cref{lem:selfcontracted} and the length bound for self-contracted curves
\cite{DaniilidisDavidDurandCartagenaLemenant2015}, the iterates have finite length. Replacing each coordinate $x_k^{(i)}$ by a rational
$r_k$ with $\abs{r_k-x_k^{(i)}}<2^{-k}$ gives a computable sequence of rationals with finite total variation and
the same limit, so the limit is d.c.e.\ \cite{AmbosSpiesWeihrauchZheng2000WeaklyComputable}.

(c) Write $a=A-B$ with $A,B$ left-c.e. Let $\varphi$ be a one-dimensional instance from (a) with limit $\frac53A$,
and $\psi$ one with limit $-\frac54B$, both with $2$-Lipschitz derivative. The matrix
$Q=\frac15\begin{psmallmatrix}3&4\\4&-3\end{psmallmatrix}$ is orthogonal and $Q^2=I$. Let
$F(x)=\varphi(u)+\psi(v)$, where $(u,v)=Qx$. Then $F$ is convex with $2$-Lipschitz gradient, and since an
orthogonal change of variables commutes with \eqref{eq:gd} and a separable function decouples, gradient descent
for $F$ from $x_0=Q(u_0,v_0)$ converges to $Q(\frac53A,-\frac54B)$, whose first coordinate is
$\frac15(3\cdot\frac53A-4\cdot\frac54B)=A-B$. For $d>2$, add $\frac12\norm{\cdot}^2$ in the remaining coordinates.

Finally, a computable instance with a minimizer has one in some rational box $B$; the restriction of $f$ to $B$ is
a computable convex function whose minimizers are minimizers of $f$, so \cref{prop:cmin-weihrauch} gives a
computable minimizer. The instance from (a) built from a non-computable left-c.e.\ real has a non-computable limit,
while $\argmin f_y\ni1$.
\end{proof}

\Cref{thm:F} separates the two faces of \cref{thm:A}. Uniformly, the limit operator of gradient descent is as hard
as $\lm$; but on computable inputs its values are confined to the d.c.e.\ reals, a class strictly below the
limit-computable ones, and the reason is geometric: self-contracted orbits have finite length. In Hilbert space
orbits need not have finite length, and whether the restriction persists for norm-convergent instances is
\cref{prob:hilbert-limits}. Combined with \cref{thm:E}(a), the corollary also says that for gradient descent in
$\R^d$ the passage from the computable data to the limit costs at most two monotone limits per coordinate, with at
most $2C_dD/\eps$ changes of mind at precision $\eps$.