1 Recap
Simulating Things
Peter Dixon March 1, 2021
A Turing machine is like a DFA with memory. It has
1. an input alphabet Σ (that doesn’t contain or ⊢)
2. a tape alphabet Γ that contains Σ and two special characters
3. states Q, including 3 special states Start s, Accept t, and Reject r 4. atransitionfunctionδ:Q×Γ→Q×Γ×{L,R}
The memory is a “tape” of “cells”. Each cell can store one symbol in Γ. The tape has a left end marked with ⊢, and infinite space to the right. When the Turing machine is given a string x ∈ Σ∗ as input, the tape will start out with ⊢ in the left end, then the symbols in x, then an infinite number of . The transition function checks the current state and tape cell, then writes something in the current cell, changes state, and moves left or right on the tape.
2 Equivalent Models of Computation
The main idea we’re going to cover today is converting between models of com- putation. This is how we compare the power levels of two models of computa- tion. If a Turing machine can simulate a DFA, then anything you could do with a DFA can also be done with a Turing machine.
2.1 Example 1
We’ll (formally) describe how to convert a DFA into a Turing machine.
Take a DFA A = ⟨Q,Σ,δ,s,F⟩. Construct a TM M = ⟨Q′,Σ,Γ,s,t,r,δ′
and ⊢
where
• Q′ =Q∪{t,r} • Γ = Σ ∪ { , ⊢}
1
• δ′(q,x)=
s, ⊢, R t, ,R r, ,R
x =⊢
x= ,q∈F x= ,q̸∈F
δ(q,x),x,R x∈Σ
This shows that Turing machines are at least as powerful as DFAs. (If you really want to be complete, you could formally prove that this TM accepts a string w if and only if the DFA accepts w.)
What’s the real goal of simulation? It’s two things:
1. If we want to show that Turing machines CAN do something, it’s useful to have a very powerful model that’s still simulatable by a Turing machine. (We only have to do the hard work of simulating the powerful model once.)
2. If we want to show that Turing machines CAN’T do something, it’s useful to have a very restricted model that’s still strong enough to simulate a Turing machine. (Again, we only have to do the hard work of simulating once.)
Analogy: once you can compile Java to assembly, you don’t have to program assembly any more.
2.2 Example 2
Now we’re going to show that you don’t change anything by making a Turing machine with a Stay option. (It can go left, right, or stay in the current cell.) We’ll call it a STM.
Obviously an STM can simulate a regular TM. We just need to show that a TM can simulate a STM. We have to somehow replace every S transition without changing what the TM accepts.
How can we replace a S transition with L and R transitions? Any time we would stay, we go right and then left.
What does that look like?
q1
0 : 1, S
0 : 1, R
q2
1 : 1, L
0 : 0, L
q1
qS2
2
q2
Last, how do we write it formally?
TakeaSTMM =⟨Q,Σ,Γ,δ,s,t,r⟩. We’llbuildaTMM′ =⟨Q′,Σ,Γ,δ′,s,t,r⟩ where:
• Q′ =Q∪{s1,…s|Q|}
δ(q, x)
• δ′(q,x) = (st,y,R)
(t, x, L)
δ(q, x) is not a S transition δ(q,x) = (t,y,S)
q = st
The first line says ”make a new state for each state in M”. I’ll leave the rest for you all to figure out.
There’s actually another solution: If the Turing machine stays in the same cell, then the next symbol it reads is whatever it just wrote. So we can figure out what the Turing machine will do next, and combine the stay transition with that.
q1 q2 q3
0 : 1, S
q1
How would you write this formally?
1 : 0, R
q3
0 : 0, R
3