Let's say we have an alphabet $\Sigma = \{a,b, \dots , z\}$

Set $A$ consists of words $x_i$ containing symbols from $\Sigma$ alphabet, which have this structure

$x_i := \alpha_i \beta_i$, where $\alpha_i$ is just 1 symbol from $\Sigma$ and $\beta_i \in \Sigma^{*}$ (can also be empty)

So the set A should look like this $A = \{ \alpha_1 \beta_1, \alpha_2 \beta_2, \dots , \alpha_n \beta_n, \dots\}$

The question is:

If the set $A$ is decidable, then should also the set $B = \{ \alpha_1, \alpha_2, \dots , \alpha_n, \dots\}$ be decidable?

My thoughts..

For the set $A$, we have a total computable function $f(x_i)$ which gives an answer, whether a given input element contains in $A$ or not. Now, when we shrink $x_i$-s and only leave $\alpha_i$ parts, we cannot use $f$ anymore. The only idea which came to my mind, is using this naive algorithm.

get input $\alpha_j$
for each $x_i \in A$
   if $\alpha_j$ is prefix of $x_i$
      return YES
return NO

And here, I guess, the problem is in for each statement. Here we enumerate all elements of the set $A$. For being able to do this, I guess we need to use some kind of mapping $\phi : \mathbb{N} \to \Sigma^{*}$ and then apply $f$ on the output to get all possible $x_i$-s. This algorithm may give a correct answer, but it also may give no answer (we will never reach to return NO). So my conclusion was B is not decidable (B is semi-decidable). But there might also be a 'better' algorithm?

..end of my thoughts.

I apologize if my thoughts are 100% wrong. That's how far I could reach.

Any help is much appreciated.

  • @Raphael, sorry about poor formatting and thanks for your constructive feedback. I tried to improve my question. Let me know, if I can improve more. In fact, this question has been asked to me by a friend of mine. I couldn't help him, that's why I tried to find some help here. I hope my added thoughts might help to notice where did I stuck. Thank you. – shcolf Jul 15 at 21:00
  • 1
    Thanks, much better now! – Raphael Jul 16 at 5:04
up vote 2 down vote accepted

You probably have to twist your head a couple of times but $B$ is decidable and it does not depend on the decidability of $A$. Note that $B \subseteq \Sigma$, i.e. a subset of your finite alphabet. Thus, $B$ is finite and hence, it is decidable.

However, this reasoning is not constructive: It is just enumerating all functions $\Sigma \to \{0, 1\}$ (that are $2^{|\Sigma|}$, i.e. finitely many), which are all computable, and one of them is the correct function although you do not know which one.

  • Ooh, I see. Thank you for your answer :) Please let me clarify this answer with a friend of mine, and only then accept it if he wouldn't have any questions. – shcolf Jul 16 at 6:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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