# Semidecidability/Decidability for strings seperated by a non alphabet symbol

I am trying to prove the following:

Let $\Sigma$ be an alphabet not containing the symbol "$;$", and suppose that $L \subseteq \Sigma^*$; $\Sigma^*$ is recursively enumerable. If this is the case language $L' = \{x \in \Sigma^*: x; y \in L \ for \ some \ y \in \Sigma^*\}$ is recursively enumerable.

which left me a little bit confused. Since $";"$ is not in the alphabet $\Sigma$ should I seperate $x$ and $y$ and show that check for $x \in \Sigma^*$ and $y \in \Sigma^*$ is recursively enumerable?

Also, will this statement be the case if we checked for being recursive instead, that is if $L$ was recursive, is $L'$ necessarily recursive as well? And is the proof of this the same with the recursively enumerable case?

Any help will be appreciated.

## 1 Answer

First, a few things that may or may not help:

• Def: A language $L\subseteq \Sigma ^*$ is Recursive (R) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$ and $0$ iff $u\not\in L$.

• Def: A language $L\subseteq \Sigma ^*$ is Recursively enumerable (RE) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$. (If $u\not\in L$, ir may return $0$ or loop forever)

• Prop: A language $L$ is RE iff there is some algorithm that enumerates $L$. One way to formalize "$\mathcal A$ enumerates $L$" would be to say that the algorithm $\mathcal A$ takes an integer $n\in \mathbb N$ and returns some $\mathcal A(n)\in L$ for each $n$, and that for any $u\in L$ there is at least one $n$ so that $\mathcal A(n)=u$ (i.e. if you look at the algorithm as a function $\mathcal A:\mathbb N \to L$, it is surjective).

• Remark: Even though the notins of R and RE seem to depend on the alphabet, they do not. If you have an algorithm $\mathcal A$ that takes a word $u\in \Sigma$ as input, you create the one that takes $u\in \Sigma'^*$ by returning $0$ if $u\not\in \Sigma$ (which is decidable) and then running $\mathcal A$. And in the other direction, you can just reuse the same algorithm.

Now, take some alphabet $\Sigma$ so that $;\not\in\Sigma$ and let $\Sigma':=\Sigma\sqcup \{;\}$.

To show that your $L'$ is indeed RE, just take the algorithm $\mathcal A$ that proves that $L$ is RE. When given $x\in \Sigma^*$, you want to know if there is some $y\in \Sigma^*$ so that $x;y\in L$. The problem with simply trying for each $y\in \Sigma^*$ is that your first call to $\mathcal A$ may never terminate and you'll have looped on a possibly positive instance. What you want to do instead is this: for $n$ from $0$ to $+\infty$, for each word $y\in \Sigma^*$ of size $|y|\le n$, run $\mathcal A$ on $y$ for $n$ steps (or seconds) and if it returns $1$, return $1$. So you're trying bigger a bigger $y$ while giving more and more time to $\mathcal A$ to finish. If there is some $y$ so that $x;y\in L$, then you'll eventually try for this $y$ and give $\mathcal A$ enough time to tell you it's the corect $y$. And if it answers yes, then clearly, there is some $y$ so that $x;y\in L$. So we just proved that $L'$ is RE.

Using the property I gave above, there is another simpler proof. You suppose that you can enumerate $L$ and want to enumerate $L'$. Well clearly, you just have to enumerate $L'$ and drop the $;$ and whatever is after it.

If you suppose that $L$ is R then $L'$ may not be R. Recall that the halting problem $HALT=\{\langle M,w\rangle|M\text{ halts on input }w\}$ is undecidable (i.e. $HALT\not\in R$). Let $BHALT:=\{\langle M,w\rangle;n|M\text{ halts on input }w\text{ in at most }n\text{ steps}\}$. Clearly $BHALT\in R$: you can just simulate $M$ on $w$ for $n$ steps and then check if the last state is final. But if you take $L=BHALT\in R$, then $L'=HALT\not \in R$.