Why can't we compute the lexicographically-least word of a given length on which a given TM halts?
Since for a given $n$, there are only finitely many strings in $\Sigma^n$, saying &quot;run $M$ on all words from $\Sigma^n$&quot; does make sense. But we need to be somewhat careful about the details here.

We could run $M$ on all $w \in \Sigma^*$ in parallel. If we do that, then (assuming that $M$ halts on at least one of them, which we may do here), there is a first word for which we learn that $M$ halts on it. But &quot;first&quot; here refers to our particular simulation, and to how long $M$ takes on the various words. This will generally not be the lexicographically first word; so this is not doing the job.

We could run $M$ on the words $w \in \Sigma^*$ in lexicographic order. But now, if $M$ doesn't halt on $0^n$, we never proceed beyond this particular simulation.


To prove that the function is indeed non-computable, mirror the proof of Rice' theorem.