The interesting thing about semi-deciding languages is that the machine answers "yes", but never answers "no". If you're sitting around waiting for the machine, you don't know if the reason it hasn't yet halted is that the input is not in the language, or that it simply needs more time.
Semi-decision might not seem very useful, but the issue isn't really one of utility. Some problems in life are only semi-decidable. For example: Are there other forms of intelligent life in the universe? This question can be answered in the affirmative (if we ever run across another intelligent lifeform), but never in the negative. True, we haven't found another intelligent lifeform yet, but maybe we will tomorrow! So semi-decision is a fact of life. The question is, are there languages that are semi-decidable for Turing machines but not decidable for Turing machines.
The conventions we will use for our Turing machine sort of split the difference between the two. They are:
A Turing Machine is a 5-tuple (Q,Σ,Γ,δ,s) where
- Q is the set of states, h ∉ Q, and Q must be finite
- Σ is the input alphabet
- Γ is the alphabet of symbols that may appear on the tape at any point in the computation, exluding the blank character □ (note that Σ ⊆ Γ)
- δ is the transition function
δ: Q×(Γ∪{□}) → (Q∪{h})×((Γ∪{□})×{L,R,S}- s is the start state, s ∈ Q
Thoughts:
Example 1: | with input alphabet {a}. | |
Example 2: | with input alphabet {a,b}. |
M' = (Q,Σ,Σ,δ',s), where
δ'(q,x) = {
(h,□,S) if x = □ and q ∈ W (q,□,S) if x = □ and q ∉ W (δ(q,x),□,R) if x ≠ □
We followed the mystery algorithm through with input machine M being our favorite DFA, the one that accepts all even length strings of a's and b's. What we discovered is that we got a TM M' that semi-decides the language of all even length strings of a's and b's. In general, given any DFA M, the algorithm produces a Turing Machine that semi-decides L(M). This leads us to the following theorem:
Theorem: Any regular language can be semi-decided by a Turing Machine.