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 notin 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
