patternMinor
Decidability of a set containing first symbols of elements of a decidable set
Viewed 0 times
containingelementsdecidablefirstdecidabilitysetsymbols
Problem
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
..end of my thoughts.
I apologize if my thoughts are 100% wrong. That's how far I could reach.
Any help is much appreciated.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#95298, answer score: 3
Revisions (0)
No revisions yet.