**Problem Detail:**

I see that Σ* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable.

What is the proof that Σ* is decidable?

###### Asked By : Charles

#### Answered By : Andrej Bauer

**Theorem:** *The set $\Sigma^{*}$ of all words is decidable.*

*Proof.* According to the definition of decidability, we must provide a computable function $d$ which takes a word $w$ and outputs $1$ if $w \in \Sigma^{*}$, and outputs $0$ if $w \not\in \Sigma^{*}$. Such a function is very easily constructed, it is $$d(w) = 1,$$ That is, because every word is in $\Sigma^{*}$, the decision function always says "yes". QED.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32726

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback