# Why can't we compute the lexicographically-least word of a given length on which a given TM halts?

I had this question in my exam. but my answer is wrong(I didn't receive explanations why...) $$f(\langle M\rangle,1^n)=\left \{ \texttt{the lexicographically smallest } x\in\left \{ 0,1 \right \}^n \cap L(M) \texttt{ if } n>100\texttt{ and }L(M)\cap \left \{ 0,1 \right \}^n \neq\varnothing \texttt{, otherwise undefined}\right \}$$

for input $$(\langle M\rangle,1^{n})$$ when $$n \geq101$$
I run the machine on all possible inputs in $$\Sigma^{n}$$ and output the first result when conditions are
met.

I was wrong and apparently the language is not computable. what did I miss?

• How do you run $M$ on all possible inputs in $\Sigma^n$? You can't do it one at a time, otherwise one execution of $M$ could not halt. If you do it in parallel and one execution with input $x$ halts and accepts, how do you know that no other execution with input $x' <x$ will accept? – Steven Feb 11 at 14:41
• @Steven Ok I understand your point. I meant in parallel(when reading the input). following your explanantion I can't confirm if some x is the minimal lexigoraphical because possibly there may be an x' in a later iteration that is smaller than x which I assumed is the smallest?thus this is not computable? – user6394019 Feb 11 at 14:49
• Yes, you can't be sure that $x$ is the smallest such input. My comment is just intuitive (non formal) argument that shows you why your approach fails. For a formal proof that $f$ is not computable see my answer. – Steven Feb 11 at 14:53

Since for a given $$n$$, there are only finitely many strings in $$\Sigma^n$$, saying "run $$M$$ on all words from $$\Sigma^n$$" does make sense. But we need to be somewhat careful about the details here.

1. 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 "first" 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.

2. 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.

Consider this version of the halting problem: given $$T$$, decide whether $$T(\varepsilon)$$ halts (where $$\varepsilon$$ denotes the empty string).

Let $$\overline{0}$$ (resp. $$\overline{1}$$) be the string containing $$101$$ zeros (resp. ones) and suppose towards a contradiction that your function is computable. Then, given $$T$$ you can construct a Turing machine $$M_T$$ that behaves as follows on input $$x$$:

• If $$x\neq \overline{0}$$ then $$M_T(x)$$ accepts;
• Otherwise $$M_T(x)$$ simulates $$T(\varepsilon)$$, and when (if) $$T(\epsilon)$$ halts $$M_T(x)$$ accepts.

It is easy to see that $$f(\langle M_T \rangle, \overline{1}) = \overline{0}$$ if $$T(\varepsilon)$$ halts and $$f(\langle M_T \rangle, \overline{1}) = \underbrace{00\dots0}_{100 \mbox{ times}}1$$ if $$T(\varepsilon)$$ does not halt.

Since $$f$$ is computable by hypothesis, we can decide the halting problem by computing $$f(\langle M_T \rangle, \overline{1})$$ and accepting iff $$f(\langle M_T \rangle, \overline{1}) = \overline{0}$$. This is a contradiction.