EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 5 1 Turing Machine (TM)
A Turing machine is very similar to a DFA. In fact, much of the terminology between DFAs and Turing machines is very similar, and like a DFA, we can also picture a TM as a graph or state diagram where each node indicates a state of the TM and the edges collectively represent the transition function of the TM.
Definition 1.1 (M recognizes language A). For a language A, we say a Turing machine M rec- ognizesAifandonlyifforallw∈A,M acceptswandforallw̸∈A,M doesnotacceptw. We define L(M) = A to be the language which M recognizes.
Copyright By PowCoder代写 加微信 powcoder
However, Turing machines are several levels of computational power stronger than DFAs (ex- pressed by the fact that the Chomsky hierarchy has levels between the languages connected to Turing machines and DFAs). In other words, there are languages which a Turing machine can recognize, but a DFA cannot. What gives this difference in power? Turing machines are different in several ways from DFAs:
• A Turing machine has an infinite array of memory (called its tape) which it can modify (more on this later), one step per entry. The input is given to the Turing machine on the tape and the Turing machine starts reading the input from its first character. After the input lies infinitely many blank symbols.
• A Turing machine may write special symbols which are guaranteed to never appear in the input. These are the symbols contained in Γ\Σ (see the formal definition in section 3). There must be at least one symbol that the TM may write which cannot appear in the input, i.e. Γ \ Σ is guaranteed to be non-empty.
• After writing a symbol, the Turing machine head (the pointer from the DFA) may look at either the left or right cell in the tape.
• After transitioning to the accept (or reject) state, the Turing machine halts and accepts (or rejects).
Based on these differences, we only need to extend how we simulate a DFA to simulate a Turing machine – we need to keep track of the tape and its contents. Like how Turing machines can be thought of an extension of DFAs, the terminology used with Turing machines is an extension of what we saw with DFAs.
Definition 1.2 (M decides language A). For a language A, we say a Turing machine M decides A if and only if the following conditions hold:
• Forallx∈A,M acceptsx.
• Forallx̸∈A,M rejectsx.
Note that for a DFA, recognizing was synonymous with deciding – any input that was not accepted was rejected. However, unlike DFAs, execution of a TM does not end until a special accept or reject state is reached. If such a state is never reached, then we say the TM is in an infinite loop. A TM that reaches an infinite loop on at least one input, by definition, cannot decide a language, but it could still recognize one (more on this in a few weeks!).1
1Or refer to Sipser’s Introduction to the Theory of Computation chapter 3
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 5 Definition 1.3 (Language A is decidable). We say a language A is decidable if there exists some
Turing machine which decides A.
Furthermore, because of how much stronger Turing machines are than DFAs, it turns out that you do not need to restrict yourself to specifying a graph to specify a Turing machine. Later we will see the Church-Turing thesis which claims anything which can be done by a Turing machine can be done by a real computer (and vice versa). This allows us to use pseudocode to specify deciders – much less tedious than specifying a graph!
Example 1.4. Let Lprimes = {p : p is prime}. We can show that Lprimes is decidable by con- structing a Turing machine which decides it (technically, we construct an algorithm then apply the Church-Turing thesis).
function primes decider(n): for i = 2 … n−1:
if i divides n: return false
return true
Example 1.5. Let LK-DEGREE = {(G = (V, E), k) | ∃v ∈ V s.t. deg(v) ≥ k} where G is a directed graph and k is a nonnegative integer. Show that LK-DEGREE is decidable by writing a decider M for LK-DEGREE.
Solution: M = “on input (G = (V, E), k): 1. For each v ∈ V :
Count the number of edges for which v is an endpoint. Double count all edges that loop from v to v. If the total count is at least k, accept.
2. Reject.”
2 Equivalence of Turing Machines
We model computers as Turing Machines in order to reason about what a computer theoretically can and cannot compute, even with limitless power and memory. When we want to prove something, it can be convenient to switch to a different representation of the problem. This section describes one such alternative representation, and proves that it is equivalent to a Turing Machine.
Definition: (1-tape) Turing Machine
Recall the specification of a (1-tape) Turing Machine. Formally, we define a (1-tape) Turing Machine as a 7-tuple (Q, Σ, Γ, qstart, qaccept, qreject, δ) where
Q := the set of states, including qstart, qaccept, qreject Σ := The input alphabet
Γ := The tape alphabet qstart := The start state
qaccept := The accept state
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 5 qreject := The reject state
δ := The transition function Fora(1-tape)TuringMachine,δmapsfrom(Q\F)×ΓtoQ×Γ×{L,R}whereF istheset
{qaccept, qreject}.
The formal definition of a 2-tape Turing machine is almost exactly the same – the only difference
is in how δ maps.
Definition: 2-tape Turing Machine
A 2-tape Turing Machine is a Turing Machine which has two infinitely-long tapes and two heads (that’s one head per tape, for a total of two heads). Formally, a 2-tape Turing Machine is a 7-tuple (Q, Σ, Γ, qstart, qaccept, qreject, δ), where
Q := the set of states, including qstart, qaccept, qreject Σ := The input alphabet
Γ := The tape alphabet qstart := The start state
qaccept := The accept state qreject := The reject state
δ := The transition function (more on this later)
We define F := {qaccept, qreject}, the set of final/terminal states. In a normal Turing Machine, we have
δ:( (Q\F) ×
Non-terminal state
Γ )→( Q × Γ ×
What’s on the tape New state Symbol to write
{L,R} )
How to move TM head
To model two tapes, we modify the transition function δ as follows:
δ:( (Q\F) ×
Non-terminal state
× Γ )→
What’s on tape 2
Symbol to write on tape 2
Symbol to write on tape 1
× {L,R} × {L,R} )
How to move TM head 1 How to move TM head 2
What’s on tape 1
Theorem: 2-tape Turing Machines and 1-tape Turing Machines are equivalent
To show that 2-tape Turing Machines and 1-tape Turing Machines are equivalent, we’ll show 1. A Turing Machine with 2 tapes can compute as much as a 1-tape Turing Machine can
2. A Turing Machine with 1 tape can compute as much as a 2-tape Turing Machine can
A Turing Machine with 2 tapes can compute as much as a 1-tape Turing Machine can
To prove this claim, it is sufficient to show that a 2-tape Turing Machine can simulate a 1-tape Turing Machine. A 2-tape Turing Machine can do this by simply ignoring the second tape!
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 5 A Turing Machine with 1 tape can compute as much as a 2-tape Turing Machine can
To show this, we’ll show that a regular (1-tape) Turing Machine can simulate the operations of a 2-tape Turing Machine. Let M be an arbitrary 2-tape Turing Machine. We want to design a 1-tape Turing Machine T to simulate M.
Schematic of the tape for T:
#··· • ···#··· • ···#
Contents of Tape 1 Contents of Tape 2
Use # to separate the 2 simulated tapes.
Use • to mark where each tape head would be in the 2-tape Turing Machine (formally, this means that we let the tape alphabet of T be the union of the tape alphabet of M and the dotted version of the tape alphabet of M). Note that this is slightly different than the version of the proof used in lecture where we added just the • on its own to the tape alphabet and let the head be the position to the right of the •
Formally, define T as the Turing Machine which accepts input w = w1, · · · , wn, and proceeds as follows:
1. Put the tape in the correct format:
# w1,···,wn # ⊥ #
2. T scans the tape from the first # to the third # to determine the start locations of each of the 2 simulated TM heads (i.e. check which symbols are under the dots).
3. T makes a second pass from the first # to the third #, updating the TM heads according to M’s transition function δM.
4. If T moved one of the heads (marked with •) to overwrite the end-of-tape marker #, it means that M would have hit a blank cell ⊥. However, if T were to simply overwrite the #, then T would have no way of knowing where the first “tape” ended and the second “tape” started!
To deal with this situation, T shifts all cells 1 space to the right, and then writes a blank symbol where the overwritten # used to be. T then proceeds as usual.
Recap: We have described a 1-tape Turing Machine T which perfectly simulates the operations of a 2-tape Turing Machine M. Because M was an arbitrary 2-tape Turing Machine, we conclude that the 1-tape Turing Machine can compute just as much as the 2-tape Turing Machine.
3 (Optional) Turing Completeness
In general, we say that a programming language is “Turing complete” if it is equivalent to a Turing Machine (i.e. the programming language can compute anything that a Turing Machine can, and a Turing Machine can compute anything that the programming language can compute). Here are some examples of Turing Complete programming languages:
• C, C++ • Python
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 5 • Java
• C++ templates (Yes, the templates themselves constitute a Turing Complete programming language!)
• Conway’s Game of Life2
You may not have known it at the time, but nearly every time you’ve written a program in a high-level programming language you’ve been reasoning about something that’s equivalent to a Turing Machine!
4 Diagonalization
As we saw in the previous section, Turing Machines are actually quite powerful. One might even wonder, “What can’t a Turing Machine do”? One important tool for reasoning about what Turing Machines can and cannot do is called a diagonalization argument.
Cantor’s Diagonalization Argument
In 1891, famously used a diagonalization argument to prove that although the set of natural numbers and the set of real numbers are both infinite, the infinity of the reals is strictly larger than the infinity of the naturals.
Cantor argued that if the set of reals and the set of naturals were the same size, then you should be able to assign one natural number for each real number to match up the elements of the two sets. In other words, you should be able to count the real numbers. (Formally, we say that a set X is countable if there exists a function f : N → X which is surjective (onto).)
For a proof by contradiction, Cantor argued that if there were as many natural numbers as real numbers, then you should be able to count the real numbers by listing them all out in a table like this:
r0=0 1 1 0 0 ···
r1=0 0 0 0 0 ··· A= r2=1 0 1 0 1 ··· r3=1 1 0 1 0 ···
Each row represents the binary encoding of one real number (each real number can be represented as an infinitely long digit sequence, e.g. 0.376 = 0.3759999 . . . , π − 3 = 0.14159 . . .), so the idea is that one should be able to count the real numbers by counting the rows of the table.
Crucially, the table is supposed to contain all of the real numbers. If the table were missing a number, then we could’t count the reals by counting the rows – our count would be too low, because our table would contain fewer rows than it should.
Cantor’s proof by contradiction proceeded by proving that the table was missing a row. Ex- plicitly, he argued that we can build a number s that’s not in the table.
But first, a bit of notation: Let b represent the complement of a binary string b. Examples: 00 = 11 and 01101 = 10010
2https://playgameoflife.com/ gives a nice description and simulation of Conway’s Game of Life. http://rendell- attic.org/gol/tm.htm gives a simulation of a Turing Machine using Conway’s Game of Life
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 5 Cantor constructed s one bit at a time, letting si = Aii (where Ai,j is the bit in the ith row and
jth column of the table A). Here is a picture of the table, with the Aii entries in bold:
r0=0 1 1 0 0 ···
r1=0 0 0 0 0 ··· A= r2=1 0 1 0 1 ··· r3=1 1 0 1 0 ···
With this particular table, we would construct s as follows:
So in this case, we’d have s = 1100···
Notice that with this construction, s differs from r1 in the 1st bit (because s1 is defined to be
A11). Furthermore, s differs from r2 in the 2nd bit (because s2 is defined to be A22). Continuing this argument, we can see that s must differ from every binary string in the table in at least one position. In other words, s is not in the table!
Recall that we had assumed that the table counted all of the real numbers (so every real number should be listed in the table). Clearly, this is impossible, because we found a real number (i.e. the number s) which isn’t in the table!
We’ve reached a contradiction, which concludes the proof: we’ve shown that we cannot possibly count all of the real numbers.
Diagonalization Arguments and Turing Machines
We used Cantor’s diagonalization argument to show that the set of real numbers is uncountably infinite; Cantor’s diagonalization argument can be extended to show that power set of a countably infinite set is uncountably infinite.
So, how does this tie back into Turing Machines? Recall that we can represent any piece of information as a binary string – including formal languages, the definition of a Turing Machine, the source code of a C++ program, and homework problems! By representing, say, a homework problem as a binary string, we can reason about whether or not we can count the number of different finite-length homework problems.
The information which we care most about in this discussion will be sets of inputs to Turing machines – in other words, languages. Observe that the set of possible inputs to a Turing machine Σ∗ is countably infinite. The set of inputs a given Turing machine accepts is just a subset of the set of possible inputs i.e. an element of the power set of Σ∗. From the diagonalization argument, there are uncountably many languages.
We are interested in studying what sorts of things a Turing Machine can possible compute. Of note is that a Turing Machine decides at most one language and that the set of Turing Machine which are deciders is countably infinite. This means that there is some language for which there is no decider. Such a language is undecidable.
s= s1 s2 s3 s4
s = (A1,1) (A2,2) (A3,3) (A4,4) s=0011··· s=1100···
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com