4
$\begingroup$

Question:

Is true that $L_1 = \{01^*0\}$ is $m$-complete in the class of decidable languages?

$L_1$ is defined as:

$$L_1 = \{01^*0\} := \{01^n0: n \in \mathbb{N}\}$$

Definition of a $m$-complete language:

A language $L^*$ is $m$-complete in the class of decidable language, if for any decidable language $L$ we have that $L \leq_m L^*$ (that is, $L$ reduces to $L^*$).

I'm really new in this realm, so I'm quite lost about how to tackle this exercise.

I'm not sure if my approach is correct but I was trying to prove that the statement is not true by using a reduction from the Busy Beaver Function to $L_1$ (then, from this reduction and from $L_1$ being decidable we would have that BB problem is decidable, which is not possible).

Let $A$ be the algorithm deciding $L_1$ and $w \in L_1$ a word with $|w| = m$ ones. Now when running $A$ on $w \in L_1$ we keep track of the number of steps $t$ it made just before halting. Since $t = m|\Gamma|^m|Q|$, where $\Gamma$ is the set of tape symbols and $Q$ is the set of states. From here we can find the number $|Q|$ of states required for printing $|w| = m$ ones...

I stopped here because I feel there is already something wrong.

First, even is we find that number $|Q|$ for which $A$ performed $t$ steps before $A(w) = \text{Accept}$, that does not necessarily mean that $|w| = m$ ones could have been achieved with a TM with lesser number of states. Second, ''knowing'' the numbers of ones I'm determining the numbers of states and not the other way around, which is as $BB$ is defined.

Another alternative I was exploring was, on input $w$, to run all TM's $T_1, ... T_n$, that return $|w| = m$ ones. Then we record the input $w$ and the description of the machine $T_i,\ (i \in [1,n])$, that had the least number of states. If we do this $\forall w \in L_1$, we end up with a UTM $T'$, such that:

$$T' = \{ \langle T^*, w\rangle: |Q|_{T^*} = \mathrm{min}(|Q|_{T_1}, ..., |Q|_{T_n}\ \text{}\}$$

Then clearly $T'$ decides $L_1$ (just have to run it on input $w \in L_1$) and at the same time allows us to compute $BB(n)$ for a fixed $n \in \mathbb{N}$ (since $n$ is encoded in the description of $T^*$).

Probably here there are some flaws in my reasoning, but in this case, do I have to wait that, on input $w$, all those TM's reach a halt or can I assume that the first machine that halted is the one with the least number of states?

I'd appreciate any help.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your approach can't succeed. You're asked whether every decidable language reduces to $L_1$ but your approach is to try to show that some undecidable language doesn't reduce to it. That would show nothing about decidable languages.

But are you sure that your definition is correct? Every language except $\emptyset$ and $\Sigma^*$ is $m$-complete by the definition you give.

Improve this answer
$\endgroup$
11
  • $\begingroup$ I was trying to show that there exist some undecidable language that also reduces to it and therefore $L_1$, as defined above, can't be $m$-complete. $\endgroup$
    – asd
    Commented Feb 25, 2017 at 22:35
  • $\begingroup$ So what if some undecidable languages reduce to it? The property you're trying to establish is that all decidable languages reduce to $L_1$, not that all languages that reduce to it are decidable. $\endgroup$
    – David Richerby
    Commented Feb 25, 2017 at 22:43
  • $\begingroup$ @DavidRicherby Are you sure? We are trying to disprove that $L_1$ is $R$-Complete, not that it is $R$-Hard. Hence if we showed that $L_1$ is $RE$-Hard by reducing from the BB problem, then, since $R\subsetneq RE$, we have $L_1\not\in R$, so $L_1$ is not $R$-Complete, but only $R$-Hard. This would be a good approach, if the statement were true, which it is not. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Feb 25, 2017 at 23:00
  • $\begingroup$ @LieuweVinkhuijzen I was working from the definition given in the question. That definition requires only that every decidable language is reducible to the language we care about, and it says nothing at all about undecidable languages. For example, the halting language meets this definition. Is that not the normal definition? (Actually, I suspect there may be something wrong with that definition, since it would seem that any language except $\emptyset$ and $\Sigma^*$ is complete by that definition...) $\endgroup$
    – David Richerby
    Commented Feb 25, 2017 at 23:08
  • $\begingroup$ @DavidRicherby That would be the approach if we wanted to prove that $L_1$ is $R$-Complete. It looks like the OP wants to prove that $L_1$ is not $R$-Complete. In that case, I believe the normal approach is to show that $L_1$ is not in $R$ by finding a problem outside $R$ - the OP has found the busy beaver problem - and reducing it to $L_1$. Then $L_1$ may or may not be $R$-Hard, but since it is not in $R$, the goal follows. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Feb 25, 2017 at 23:27

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.