World's most popular travel blog for travel bloggers.

# [Solved]: Prove Σ* is decidable

, ,
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?

#### 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.