Σ_{0} ⊆ Σ – {#,>}The Σ_{0} alphabet, such as our usual {a,b} is considered the acceptable alphabet for input strings and is meant to avoid other "special purpose" symbols, such as the obvious blank symbol, #, > as well as others we may want to add. The various operations that a TM can do with an input string require a certain standard starting configuration with w on the tape. We can use either this one
>wor this one:
>#w
Decide a Language
According to the textbook a TM which decides a language has two dedicated halt states: Y and N. Suppose L is a language over Σ_{0}. A TM, M, decides L if, for all strings w ∈ Σ_{0}* , when placed on the tape in the starting configuration:- if w ∈ L, M halts in state y
- if w ∉ L, M halts in state n
Σ = Σ_{0} ∪ { #, >, Y, N }and that a TM decides L, if for all strings w, when placed on the string in the starting configuration:
- if w ∈ L, the TM halts with configuration >Y
- if w ∉ L, the TM halts with configuration >N
Closure of recursive languages under complementation
We can also easily see that if L is recursive, then so is the complement of L. From a TM, M which decides L, we can create a machine deciding its complement:Deciding AnBnCn
Here we're going to add a marker symbol:Σ_{0} = { a,b,c } Σ = Σ_{0} ∪ {#,>,d,Y,N}This is the diagram from the textbook:
#aaabbbccc #daadbbdcc #ddaddbddc #ddddddddd #ddddddddd#Here's a sample of a unsuccessful run. On the second "R loop" it goes all the way to the end, where it sees a blank and fails:
#aaabbcc #daadbdc #ddadddd #ddddddd#Another failure is:
#accc
#dccc
Unfortunately, it appears that the authors have made an error
because this machine will say that
abcabcis in the language. After the first pass, it changes:
#abcabc ⇒ #dddabcIt would then scan across the d's and proceed again:
#dddabc ⇒ #ddddddNow it scans across the d's, sees a blank and terminates in the yes state. The following modification is a suggested fix, forcing the machine to move past the final c group, in which case it must see a blank:
Make it write Y/N
If you wanted to make it "write Y/N" instead of just entering the y/n state what would be different?Compute a Function
We have the Σ_{0} ⊆ Σ as the input alphabet, and we can also refer to Σ_{1} ⊆ Σ as the output alphabet. Using these, consider a function:f: Σ_{0}* → Σ_{1}*A TM computes f if, for all w ∈ Σ_{0}*, when w is placed on the tape in the starting configuration,
>wthe TM halts in a final configuration of the form:
>f(w)Again, we could just as well prepend a blank before the input and output, expecting starting and final configurations to be:
>#wthe TM halts in a final configuration of the form:
>#f(w)In particular, we can say that deciding a language L is equivalent to computing the function:
f: Σ_{0}* ⇾ {Y,N}* f(w) = Y if w ∈ L = N if w ∉ LThus, using the Y/N write method for deciding a language is, in some sense, preferable to the y/n halt state method, because it makes deciding a language simply computing a specific function.
Numeric Computation
The textbook goes immediately to binary notation for numbers, which matches computer arithmetic, but this is usually not presented as the initial notion of a number. Traditionally, one starts with unary notation:1111 = 4, etc. ε = 0The authors present the binary version of increment in Example 4.2.3, which is simply the standard ripple-carry adder. We can also talk about computing a function of more than one argument, f(x,y). Once again, assume a standard starting configuration like:
>#x#yIt means that we must halt in a final configuration:
>#f(x,y)In unary, for example, the concatenation function
f(x,y) = xyserves as the addition function.
A TM can use a partial function
A TM transition function being a partial function means that there are input pairs for which the transition function is not defined.δ(non-halting-state, symbol) = UNDEFWe can easily compensate for such an omission by adding a new dedicated "run forever" state, R:
δ(R,σ) = (R,σ) ∀ σ ∈ ΣWith this addition, simply send a missing transition to this state with no tape change, i.e.,
δ(non-halting-state, symbol) = (R, symbol)The simplest machine that we can create which runs forever is this:
RunForever = ( {s,h}, Σ, {}, s, {h} )There are start and halt states, but no transitions, implying that all transitions go to some "run forever" state.
Accepting a Language
A TM accepts or semidecides L if, for all w ∈ Σ_{0}*, the machine halts when started with the initial tape configuration if and only if w ∈ L, i.e.,- if w ∈ L, then (s, >w) ⊢* (h, ...), for some h ∈ H
- if w ∉ L, then (s, >w) ⊢* ... "runs forever," i.e., it never reaches a halt state
M↓w if M halts on input w
M↑w if M runs forever on input w
M↑w if M runs forever on input w