2
$\begingroup$

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 \}$$

I answered it is computable.
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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – Steven
    Commented Feb 11, 2021 at 14:41
  • $\begingroup$ @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? $\endgroup$
    – user6394019
    Commented Feb 11, 2021 at 14:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Commented Feb 11, 2021 at 14:53

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.