The Australian National University Semester 1, 2022 Research School of Computer Science Tutorial 7
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial.
Exercise 1 Closure Properties of Recursive Languages
Copyright By PowCoder代写 加微信 powcoder
Let Σ be an alphabet, and let L1 ⊆ Σ∗ and L2 ⊆ Σ∗ be recursive languages. Are the following languages recursive?
Solution. For the following solutions, we let M1 and M2 denote total1 Turing machines that recognize L1 and L2 respectively.
1. L1 ∪ L2
Solution. Yes, for a string x, run M1(x). If M1(x) accepts, then accept x. Otherwise, run M2(x)
and accept iff M2(x) does.
2. Lc1 := Σ∗\L1
Solution. Yes, accept iff M1(x) rejects.
3. L1 ∩ L2
Solution. Yes, for a string x, run M1(x). If M1(x) accepts, then run M2(x) and accept iff M2(x) does. Otherwise, reject.
4. (hard) L1L2
Solution. yes, for a string x = x1 . . . xn of length n, form every possible partition of x into two
strings x = αβ.
α1 =x1 α2 = x1x2
β0 =x1…xn β1 =x2…xn β2 = x3 …xn
… … αn−1 = x1 …xn−1 βn−1 = xn αn =x1…xn βn =ε
Accept if there exists i such that M1(αi) and M1(βi) both accept (Just try all of them one after the other until one works.) Reject if no such i exists.
5. (hard) L∗1
Solution. Yes, let x be a string of length n. If x is empty, then x ∈ L∗1, and we are done. Assume
x non-empty.
Totestifx∈L∗1,weneedtocheckifthereexistsacollectionofstringsy1…yk suchthatx=y1…yk and each yi ∈ L1. There are finitely many ways to write such a decomposition of x. (Consider the fact that such strings that could possibly make up x must be drawn from the set {y : |y| ≤ n : y ∈ L1}, with at most |Σ|n elements.) Without loss of generality, we can assume each of the yi are non empty, as any decomposition that uses empty strings could also be achieved without them, and if no decomposition exists, allowing the use of empty strings doesn’t help. The maximum number of strings required is n, as the yi’s are non empty.
So, an upper bound on the number of ways to decompose x is (|Σ|n)n. Try them all, and accept iff there is a decomposition satisfying the above property.
1always eventually halting on any input
Exercise 2 Closure Properties of Recursively Enumerable (RE) Languages
Let Σ be an alphabet, and let L1 ⊆ Σ∗ and L2 ⊆ Σ∗ be recursively enumerable languages. Are the following languages recursively enumerable?
Solution. For the following solutions, let M1 and M2 be Turing machines with the properties that L(M1) = L1 and L(M2) = L2 respectively.
1. L1 ∪ L2
Solution. Yes, for a string x, run M1(x) and M2(x) in parallel (by alternating between simulating
M1(x) and M2(x), we can pretend to run both in parallel. Accept iff either one accepts.
2. Lc1 := Σ∗\L1
Solution. No, as otherwise all recursively enumerable languages would be recursive, as we would have a decision process to test of a string is outside a RE language if this closure property were true. A counter example would be the universal language
Lu = {⟨M, w⟩ : M accepts w}
Clearly Lu is RE as we can test acceptance by decoding ⟨M,w⟩ to obtain the machine M, and the string w, and simulating M(w), accepting if M(w) does. But if the complement was also RE, then Lu is decidable, and hence we can solve the halting problem (by taking any machine, and making all of its states accepting, it accepts iff it halts.)
3. L1 ∩ L2
Solution. Yes, for a string x, simulate M1(x) and M2(x) in parallel, accept if M1(x) and M2(x)
Solution. Yes, perform the same trick as we did for the case of recursive languages, but now we run all the possible splittings in parallel, and accept if any one machine accepts.
Solution. Yes, perform the same trick as recursive, but test all possible decompositions in parallel
(which as discussed before, there are finitely many.) Accept if any valid decomposition is found.
Exercise 3 More Decideability Problems
Classify the following languages as decidable (recursive), recursively enumerable, or not recursively enu- merable. 2
1. (hard) Ld = {⟨M⟩ : M is a TM that does not accept ⟨M⟩}
Solution. Not recursively enumerable.
Suppose it were. Then there exists a machine D such that, when fed a string x, if x is the encoding of a Turing machine X such that X(x) rejects, then D(x) accepts.
The machine D must have some encoding, call it d. Is d ∈ Ld?
Assume d ∈ Ld. Then d is the encoding of a Turing machine that doesn’t accept it’s own encoding.
So D(d) fails to accept, and hence d ̸∈ Ld, a contradiction.
Assume d ̸∈ Ld. Then it is not the case that d is the encoding of a Turing machine that fails to accept it’s own encoding. So either d is not the encoding of a Turing machine (a contradiction, d is the encoding of D) or d encodes a machine that accepts it’s own encoding. So D(d) accepts, and d ∈ LD, a contradiction.
In either case, we get a contradiction. Hence Ld is not RE.
2Note that languages can only contain strings, so ⟨·⟩ means to take the thing inside the brackets, and encode it as a binary string.
2. Lcd ={⟨M⟩:M isaTMthataccepts⟨M⟩}
Solution. Recursively enumerable. Construct a machine K that takes an input x. If x is not the encoding of a Turing machine, halt and reject. If x is the encoding of a Turing machine, (representing machine X), then simulate X(x), and accept if X(x) does.
Hence, L(K) = Lcd, and Lcd is RE.
However, it cannot be recursive, as recursive languages are closed under complements, and hence
Ld would be recursive, a contradiction.
3. L0 = {⟨M⟩ : M eventually prints a zero on the tape}
Solution. Recursively enumerable.
Construct a machine K that takes an input x. If x is not the encoding of a Turing machine, halt and reject. If x is the encoding of a Turing machine, (representing machine X), then simulate X(x), and accept if X(x) ever prints a zero.
Hence, L(K) = L0, and L0 is RE.
Now, suppose that L0 were recursive. For a given machine M and input w, define the machine TM,w
to do the following:
TM,w ignores the input, and simulates the action of M(w) (but whenever M(w) would print a zero, TM,w stores it on the tape as some other special symbol not used by M (say, $.) Whenever TM,w reads the special symbol $ from the tape, it indicates to the simulation of M(w) that a zero was read. After running M(w) (if that ever happens), TM,w prints a zero, and halts.
It’s clear from construction that TM,w prints a zero iff M(w) halts. So since L0 is decidable, the halting problem is decidable, a contradiction.
4. (hard) LΛ = {⟨M⟩ : M never modifies the tape when fed blank input}
Solution. Recursively (strangely enough!)
Let ⟨M⟩ be a Turing machine. It is decidable to compute the number of state of M. Say that M has n states. Run M on empty input for n + 1 time steps. If it has modified the tape in that time, then we know ⟨M⟩ ∈ LΛ. If it hasn’t, check if it’s halted by now. If it has, then it hasn’t modified the tape, and ⟨M⟩ ̸∈ LΛ If it hasn’t yet halted, then by pidgeon-hole principle, it must be in a state that’s already been visited. Since the TM is in a state it’s been in before, with the tape in the state configuration as before, it’s forced to do precisely the same thing it did last time it was in this configuration, and it will be trapped in a loop, running forever, never writing to the tape. Hence ⟨M⟩ ̸∈ LΛ.
Since we have a decision process to test if ⟨M⟩ is in LΛ or not, that makes this language recursive.
5. (hard) Does your answer for LΛ contradict Rice’s Theorem?
Solution. No, as Rice’s Theorem relates to properties of recursively enumerable languages, whereas LΛ is a property of the behaviour of the Turing machine, not the language that the machine recognizes.
Exercise 4 Busy Beaver
For the purposes of this exercise, we restrict ourselves to psuedo3Turing machines of the form Bn = (Qn,Σ,Γ,δ,q0,B,F) (for some n ≥ 1) where
1. Qn = {q1,q2,…,qn,H}
2. Σ={0,1}
3. Γ={0,1}
4. δ : Qn ×Γ → Qn ×Γ×{L,R}, and δ is always defined for all states q1,…,qn, and δ is never defined for the state H (called the halting state).
3As we are allowing our blank symbol to also be in the input.
5. q0 = q1. 6. B = 0
7. F = {H}
That is, Turing machines where the input is a binary string the tape symbols are 0 and 1, the tape head must move left or right on each transition, and the machine halts if and only if it is in state H.
We call such a Turing machine a Beaver machine.
1. Convince yourself that (see previous tutorial if required) Beaver machines are of equal expressiveness
power as “standard” Turing machines (up to reencoding the input string). No proof required.
Solution. You can convince yourself of this by checking the previous tutorial, or talking to someone about it.
2. Show that for each n ≥ 1, there are precisely (4(n + 1))2n many Beaver machines with n states. Solution. For n states, consider δ(q,γ). There are n choices for the state q (as we cannot choose
q = H) and two choices for γ (merely 0 or 1).
For each possible input, there are n + 1 choices for the new state (as we could now choose H), two choices for the new tape symbol, and two choices for the direction to move the tape head, for a total of (n + 1) × 2 × 2 = 4(n + 1) options. Hence, the question reduces to “how many functions are there with 2n inputs and 4(n + 1) outputs”, for which the answer is (4(n + 1))2n.
For each n, there are finitely many Beaver machines. Consider what would happen if we ran those Beaver machines on empty input (a tape full of zeros). Some of the machines would halt, and some would run forever. We call the Beaver machine with n states that, given empty input, runs for the longest number of transitions while still halting the Busy Beaver with n states.
Define BB(n) : N≥1 → N to take n as input, and return the number of transitions the Busy Beaver with n states runs for. We call BB the Busy beaver function4.
3. Show that BB(n) is well defined.
Solution. There are finitely many Beaver machines with n states. Discard those that run forever. Of those that are left, enumerate them in a list, M1, . . . Mk, each of them runs for some number of transitions, and then halts. Suppose that machine Mi runs for Ti steps. Then ∀i, Ti < ∞, and we can take the maximum of finitely many finite numbers. So max1≤i≤k Ti is well defined, and precisely equal to BB(n), by definition. Hence BB is well defined.
4. (hard) Show that BB(n) is incomputable (that is, there does not exist an algorithm to compute the busy beaver function.) (Hint: Given the ability to compute BB(n) for all n, find a way to solve the halting problem.)
Solution. We’ve established that beaver machines are just as powerful as standard Turing ma- chines, which can implement any algorithm. First, note that any Turing machine M with input w can be simulated by a Beaver machine MB. The beaver machine MB ignores the input, and simulates running the machine M on the input w. If I could somehow determine by an algorithm if MB halted on empty input, then I could decide if M halts on w, and thereby solve the halting problem.
Now, MB has some number of states, say n many. Compute BB(n), which will be a finite number. Run BB(n) many transitions of MB fed empty input. If MB has halted by then, then we know it halts (obviously). If MB hasn’t halted by then, it never will, as all halting n-state beaver machines must halt in BB(n) transitions or less.
Hence, we have a decision process for checking if MB fed empty input runs forever, and hence by the above, we can solve the halting problem, a contradiction.
Hence, BB(n) is incomputable.
5. (hard) Let f : N≥1 → N be a function. Assume that f is computable (that is, there exists an
algorithm to evaluate f(n) for any n.) Prove that5 BB(n) ̸= O(f(n)).
4Rado, T., 1962. On non-computable functions. Bell System Technical Journal, 41(3), pp.877-884.
5Recall that f(n) = O(g(n)) if there exists some constant C, and some n0, such that for all n ≥ n0, f(n) ≤ Cg(n).
What can we conclude from BB(n) ̸= O(f(n)) for any computable f.?
Solution. Assume for contradiction that there exists computable f such that BB(n) = O(f(n)).
Then there exists some C, and some n0 such that for all n ≥ n0, BB(n) ≤ Cf(n).
Clearly, if f is computable, the function n → Kf(n) is also computable, for any value of K (just
compute f and then multiply by K afterwards.)
So, there exists an algorithm to compute Cf(n) for any n.
Take any beaver machine MB. WLOG the number of states n in MB satisfies n ≥ n0, as if it doesn’t, just add dummy states that don’t do anything.
Now, compute C (f (n)), and then simulate MB for C (f (n)) many transitions. If it halts in that time, then it halts. If it hasn’t halted after C(f(n)) many transitions, then it never will, as if it was going to halt, it has to do so in no more than BB(n) transitions, and BB(n) ≤ C(f(n)). Hence we have a decision process to check if a beaver machine halts, and by the previous question that is equivalent to solving the halting problem, a contradiction.
Hence, since BB(n) ̸= O(f(n)) for any computable f, it must be the case that BB(n) grows faster than any computable function. Polynomials, exponentials, factorials, nested powers, tetra- tion, Knuth up-arrow notation, BB(n) out grows them all. Any function you care to name (that’s computable), and BB(n) will outpace it!
6. Show that BB(1) = 1.
Solution. We’ve only got one state to work with (ignoring the halt state) so all our state has to
be encoded as bits on the tape.
Initially, we read a zero. Regardless of what we write or what direction we move in, if we transition back to the same state, the Turing machine will do exactly the same thing next transition, as it will be in the same state reading the same input (a different zero), and infinite loop.
The only option is to transition to the halting state immediately. Hence, BB(1) = 1.
7. (hard) Show that BB(2) ≥ 6. Solution.
Here is a n-state beaver machine that takes exactly 6 transitions to halt given blank input. (In fact, this is the best that can be done with only 2 states (ignoring the halting state), but proving this is nasty, you’d have to check every other 2-state beaver machine and verify they if they run for more than 6 transitions, they never halt.
0,1 1,R 1,L
8. The Goldbach conjecture states that every even number n ≥ 4 is the sum of two primes. For example, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 7 + 3, 12 = 5 + 7, 14 = 11 + 3, . . ..
Though it seems to be true, we don’t know for sure if it is.
Show that if you could compute BB(n) for all n, it would be easy to resolve the Goldbach conjecture.
(Hint: How could you use the BB function to check if a counter example to Goldbach’s conjecture exists?)
Solution. There is an algorithm that searches for counter examples to Goldbach’s conjecture, merely take each even number n, (starting from 4), and check if n − p is prime for all primes p < n.
If a counter example exists, halt and return n. If we find a decomposition for n, add 2, and try again.
This algorithm will halt if and only if the Goldbach conjecture is false. From above, we can use the Busy Beaver function to solve the halting problem, and hence we can resolve the Goldbach conjecture.
Aside: At time of writing, it is known that
BB(3) = 21
BB(4) = 107
BB(5) ≥ 47176870 BB(6) > 7.4 × 1036534
BB(7) > 102×10101018705353
Furthermore, the bound on BB(7) is obtained by taking the busiest known beaver for 6 states, and extending it with an extra state. The best known bound on BB(7) is likely very, very weak, and the true value is probably much greater.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com