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?

  • 3
    $\begingroup$ This is a very trivial question. What words are in $\Sigma^*$? What words are not in $\Sigma^*$ (if any)? So how would you write a decider for $\Sigma^*$? $\endgroup$ – Hoopje Nov 5 '14 at 8:04
  • $\begingroup$ The definition of decidability pretty much answers the question. (At least after reading Hoopje's comment.) $\endgroup$ – Raphael Nov 5 '14 at 17:05

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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