0017 Computational Complexity problem sheet 1.
1. A quadratic in x over the integers has the form q(x) = ax2 + bx + c, where x is a variable a,b and c are integers. Suppose our decision problem has as set of instances all the quadratics over the integers, the
‘yes’ instances being those for which an integer x exists with q(x) = 0. Design a suitable encoding system by which this problem could be tackled on a Turing machine. (It’s not necessary to design the Turing machine.)
Solution: Every such quadratic is exactly specified by three integers a,b,c. Therefore, any encoding system that allows for the encoding of three consecutive integers is enough. We show an encoding system with alphabet Σ = {0, 1}. A positive number n is encoded as a string of 1s of length n. A negative number −n is encoded as 0 followed by a string of 1s of length n. The number zero will be encoded as 000. A triple of numbers a, b, c will be encoded as the encodings of a, b, c separated by 0. So the quadratic x2 − 2x + 3 would be represented by the string 100110111.
Copyright By PowCoder代写 加微信 powcoder
2. Suppose our alphabet Σ consists of the symbols a, b and c.
(a) Design a Turing machine T that halts and succeeds if and only if the input contains the sequence ab and halts and fails otherwise.
(Assume for simplicity the input always consists of a finite string of characters from Σ followed an infinite number of blanks.)
(b) (review) What regular expression describes the language decided by T?
a,→ Y b,→ q1
q0 ⊔,→ q2 ⊔,→ N {b, c}, →
(b) (a|b|c)∗ab(a|b|c)∗
Answers Not to be printed
3. Reminder: A language is decidable if and only if there is a Turing machine that decides it. A language is recognisable if and only if there is a Turing machine that semi-decides it (halts when the input is in the language, fails to halt when the input is not in the language).
Question: Can a language exist that is decidable but not recognisable? Give reasons.
Solution: No. Suppose such a language exists. It is decidable, thus there is a TM M that decides it. We can modify this TM by replacing the halting state N with an infinite loop. The new TM recognises the language by definition, leading to a contradiction. (Note: Languages do exist that are recognisable but not decidable but proving this involves a useful mathematical trick which will be demonstrated in lectures later in the course.)
4. Suppose we define a class C of computational devices similar to Turing machines but without the ← command, so the tape head can never move left, only right. (More formally we are demanding that δ : (Q\H)×Σ → Q × (Σ ∪ {→}) instead of δ : (Q \ H) × Σ → Q × (Σ ∪ {←, →}) as in the usual definition).
(a) Give an informal argument as to why the model of computation defined by C is not equivalent to the one defined by the class of Turing machines with the standard definition.
(b) (Hard) Give a formal proof of the same proposition.
(c) Does it make any difference to the model of computation defined by C if instead of removing ← altogether we replace it with a − command which keeps the tape head in place? Give informal reasoning.
(b) Let L be the language over the alphabet Σ = {0, 1} consisting of all strings with equal numbers of 1s and 0s. It is clear that there is a TM M in the standard model that decides L.
Suppose there is a TM M′ in the model without ← that also decides L, and suppose it has n states. We now claim that when M′ processes a string, it must reach the second blank position on the tape (i.e., the first one to the right of the input). To see this, suppose that M′ processes a string s, but halts before it reaches the end of the input. In that case, M′ must give the same result on any input string starting with s; after all, the machine never considers the characters on the tape to the right of s: it cannot have visited those characters, because it would have no way to go back! If s is accepted by M′, then we can create a string t
Answers Not to be printed
such that st ̸∈ L; since this string is accepted by M′, we have found a contradiction, and hence our assumption that M′ does not reach the end of s must be false. A similar argument applies if s is rejected by M′.
Let the strings s1, . . . , sn+1 consist of the same number of 1s as their index and no 0s. Clearly M′ must reject these strings. For 1≤i≤n+1,letqi bethestatethatM′ isinwhenitreaches the second blank position on the tape. Since we have n + 1 such qi, and M′ has only n states, at least two of them must be the same (this is called the pigeonhole principle). Suppose these are qx and qy (for x < y). We consider the strings s′x and s′y produced by concatenating y 0s to each of sx and sy. Since M′ is in the same state for both when it finishes reading the 1s, it must give the same answer when it finishes the whole string, because the remainder of the input is also the same. This is impossible as s′y is in L and s′x is not. We have now reached a contradiction with the assumption that there exists a TM M′ in the modified model that decides L, and hence such an M′ cannot exist. This shows that the computational power of these models differs.
(c) The TM model with a − command is equivalent to the one missing the ← command altogether, since we can simulate the − command by writing again the symbol that is currently under the tape head. Since the TM model without ← is not equivalent to the standard one, neither is the model with −.
5. An Enumerator is a Turing machine attached to a printer subject to the following additional constraints:
• there is no halt state.
• there is a distinguished state ‘print’.
• the tape starts blank.
• whenever the machine enters the ‘print’ state the current contents of the tape are printed by the printer. I.e, the contents of the tape immediately following “◃” up until the first blank symbol “⊔”.
In other words an enumerator starts with a blank tape on which it writes various strings from a given alphabet, occasionally printing one off. It may print out the same string more than once. The language enumerated by an enumerator E is the collection of all the strings printed by E.
(a) Describe an enumerator that generates the language Leven:={x∈Σ∗ :|x|iseven}
over the alphabet Σ = {1}. 3
Answers Not to be printed
(b) (Hard) Prove that a language L is recognisable if and only if there is some enumerator E that enumerates it.
(b) We first prove that if L is recognisable then there is an enumerator E that enumerates L. We now describe how we can construct E. E uses two more TMs as components. The first one is the machine M that semi-decides L which is provided by the assumption that L is recognisable. The second one is a machine S that generates all strings that can be constructed with a given alphabet Σ. It is not trivial to construct S, but one can easily write Java code that does this, say by generating all strings of length 1 in lexicographic order, then of length 2, etc. The Church-Turing thesis guaranties that there is a TM S that computes the same function. This machine is effectively the enumerator of Σ∗.
E works as follows. We keep a set Q of strings from Σ∗. Initially Q is empty. The machine S is executed to produce all strings from Σ∗ that have length 1. These strings are added to Q. M is then executed one by one on all strings in Q for one step. For every string in Q, if M accepts it, then E goes into its ‘print’ state and the string is removed from Q.
The machine S is now executed to produce all strings from Σ∗ that have length 2 and these strings are added to Q. M is then executed one by one on all strings in Q for two steps. For every string in Q, if M accepts it, then E goes into its ‘print’ state and the string is removed from Q. This process is repeated continuously. In nth iteration S generats strings of length n and they are added to Q. M is executed for n steps and those strings from Q that are accepted by M in this iteration are printed by E and removed from Q.
It is easy to see to show that E is the enumerator of L.
We now prove that if we there is an enumerator E for a language L then L is recognisable. Suppose we have an enumerator E for the language. We can convert E to a TM that runs the enumerator and whenever the print state is entered, the input string is compared to the tape contents; if they are the same,
q ⊔,1 q 1,→ q ⊔,1 q 0123
In particular, let q0 be the ‘print’ state.
Answers Not to be printed
the machine accepts and halts, if not it continues running the enumerator.
Answers Not to be printed
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com