2022-CS370FZ-January
Q1
(a) Give self-contained definitions of the following languages/sets: (the acceptance problem), (the halting problem), and TM M decides Language L.
Lecture 3 - = { ⟨M, w⟩∣M is a TM and M accepts w. }
Lecture 3 - = { ⟨M, w⟩∣TM M halts on input string w. }
??? - TM M decides Language L = { ⟨M, w⟩ | TM M accepts string w if w is in L, and M rejects w if w is not in L}.
(b) Show that is recognizable (construct a recognizer for it).
Lecture 3 U= “On input ⟨M, w⟩, where M is a TM and w is a string:
- Simulate M on input w.
- If M ever enters its accepts state, accept; if M ever enters its reject state, reject .”
(c) Show that is undecidable. (You are required to use the diagonalization technique)
Lecture 3 Assume we have a list of all possible Turing machines M1, M2, …and all their descriptions across the columns ⟨M1⟩, ⟨M2⟩ .…
The entries tell whether the machine in a given row accepts the input in a given column.
Next, We add which computes the opposite of the diagonal entries to the table.
The contradiction occurs at the point of the question mark where the entry must be the opposite of itself. Therefore, is undecidable.
Is recognizable? Explain your answer.
Lecture 3 According to (b), we know that is Turing-recognizable.
If also were Turing- recognizable, would be decidable.
However, according to (c), is not decidable, so must not be Turing-recognizable.
Q2
(a) Give the statement of Rice’s Theorem.
Lecture 4 Let be any nontrivial property of the language of a Turing machine. Prove that the problerm of determining whether a given Turing machine’s language has property is undecidable.
Lecture 4
Suppose that C is a proper, nonempty subset of the class of all recursively enumerable languages. Then the following problem is undecidable: Given a Turing machine M, is L(M) ∈ C?
(b) Prove Rice’s Theorem (you can use the recursion theorem).
Introduction to the Theory of Computation Assume that some TM decides a property , and satisfies the conditions of Rice’s theorem. One of these conditions says that TMs and exist where and . Use and to construct TM:
= “On input :
- Obtain own description using the recursion theorem.
- Run on .
- If accepts , simulate on . If X rejects , simulate on .”
If , then accepts and . But , contradicting
, because agrees on TMs that have the same language.
Therefore, our original assumption is false. Every property satisfying the conditions of Rice’s theorem is undecidable.
Lecture 4
Let is a decidable language satisfying the properties and be a TM that decides .
= “On input :
- Use and to construct the following TM
- Simulate on . If it halts and rejects, reject. If it accepts, proceed to stage 2.
- Simulate on . If it accepts, accept.”
= “On input :
- Use TM to deterimine whether . If YES, accept. If NO, reject.”
Therefore iff accepts .
Lecture 4
Assume that and there is a language semidecided by machine .
We shall reduce the halting problcm to the problem of deciding whether the language semidecided by a given Turing machine is in C.
Construct a Turing machine
- On input , simulates the universal Turing machine on input
- If it halts, then , instead of halting, goes on to sinulate on input x
- If either halts and accepts, or never halts, depending on thc behavior of on x
Therefore, the language semidecided by
is in class if and only if halts on input , i.e., we achieve the proof of initial assumption.
(c) Give the definitions of the following concepts: (1) Language A is mapping reducible to language B. (2) Language A is Turing reducible to language B.
Lecture 5 - Language A is mapping reducible to language B, written , if there is a computable function , where for every ,
Lecture 5 - Language A is Turing reducible to language B, written , if A is decidable relative to B.
(d) Show that
Lecture 5 Assume that TM decides . Construct TM to decide :
= “On input ⟨M,w⟩, an encoding of a TM and a string :
- Run TM on input ⟨M,w⟩.
- If rejects, reject.
- If accepts, simulate on until it halts.
- If has accepted, accept; if has rejected, reject.”
Clearly, if decides , then decides . Because is undecidable, also must be undecidable.
Q3
(a) Give the definitions of the following classes: Class P and Class NP.
Lecture 6 - P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine. In other words, .
Lecture 6 - NP is the class of languages that have polynomial time verifiers. In other words, .
(b) Give the definitions of the following sets: PATH, SAT, and CLIQUE. Your definition should be self-contained (e.g. for CLIQUE, explain what a k-clique is).
Lecture 6 - PATH = { ⟨G, s, t⟩ | G is a directed graph that has a directed path from s to t }
Lecture 6 - SAT = { ⟨Φ⟩ | Φ is a satisfiable boolean formula }.
- A boolean formula is satisfiable if some assignment of 0s and 1s to the variables makes the formula evaluate to 1.
Lecture 6 - CLIQUE = { ⟨G, k⟩ | G is an undirected graph with a k-clique }
- A clique is a subgraph, where in every two nodes are connected by an edge. A k-clique is a clique that contains k nodes.
(c) Show that CLIQUE is in NP (give a verifier or a nondeterministic polynomial time Turing machine that decides CLIQUE).
Lecture 6 V = “On input ⟨(G, k), c⟩ :
- Test whether c is a set of k nodes in G.
- Test whether G contains all edges connecting nodes in c.
- If both pass, accept; otherwise, reject.”
(d) Recall the proof 3SAT is polynomial time mapping reducible to VERTEX-COVER (3SAT≤P VERTEX-COVER). From the following ϕ construct the associated graph G. Explain how to obtain an 8-vertex-cover for G from a satisfying assignment for ϕ.
Lecture 6 First, put the nodes of the variable that correspond to the true literals in the assignment into the vertex cover (i.e., 2 nodes). Then, select one true literal in every clause and put the remaining two nodes from every clause into the vertex (i.e., 2 x 3 = 6 nodes).
Now, we hare 8 nodes. They cover all edges because every variable edge is clearly covered, all three edges within every clause are covered,and all edges between variable and clause are covered. Hence, G has an 8-vertex-cover.
2023-CS370FZ-January
不再写部分（标粉色）重复出现的题目
Q1
(c) Show that a language is decidable iff it is Turing-recognizable and co- Turing-recognizable.
Lecture 3 If both and are Turing-recognizable, we let be the recognizer for and be the recognizer for .
= “On input :
- Run both and on input in parallel.
- If accepts, accept; if accepts, reject.”
Every string is either in or . Therefore, Either or must accept . So, is a decider for and is decidable.
Q2
(c) Give self-contained definitions of the following concepts: an oracle TM
Lecture 5 An oracle for a language is an external device that is capable of reporting whether any string is a member of .
An oracle Turing macbine is a modified Turing machine that has the additional capability of querying an oracle.
Q3
(c) Show that .
Lecture 6 A polynomial time algorithm for PATH operates as follows.
= “On input where is a directed graph with nodes and :
- Place a mark on node .
- Repeat the following until no additional nodes are marked.
- Scan all the edges of . If an edge (a, b) is found, going from a marked node to an unmarked node , mark node .
- If t is marked, accept. Otherwise, reject.”
(d) Recall the proof 3SAT is polynomial time mapping reducible to CLIQUE (3SAT≤P CLIQUE). From the following ϕ construct the associated graph G. Explain how to obtain a 3-clique for G from a satisfying assignment for ϕ.
Lecture 6 First, select one node corresponding to a true literal in the satisfying assignment. If more than one literal is frue in a particular clause, choose one of the true literals arbitrarily. The number of nodes selected is 3.
Then, each pair of selected nodes can be joined by an edge because no pair fits one of the exceptions. They could not be from the same triple because we selected only one node per triple. They could not here contradictory labels because the associated literals were both true in the satisfying assignment.
Hence, G contains a 3-clique.
测试题
(1) Give the definitions of the following classes
Big-O notation
Lecture 6 Big-O notation says that one function is asymptotically no more than another.
In other words, means that, for any real number , a number exists, where for all .
Small-O notation
Lecture 6 Small-O notation says that one function is asymptotically less than another.
In other words, means that, for any real number , a number exists, where for all .
A verifier
Lecture 6 A verifier for a language is an algorithm , where = { | accepts for some string }.
Nondeterministic TM M semidecides a Language L
Lecture 2 semidecides if the following holds for all
- if and only if accepts .
设有一个图灵机 和 一个语言 ，这个语言由特定符号组成，但不包括特殊符号 。我们说图灵机“半决定”这个语言：对于任何一个由这些符号组成的字符串 ，如果 属于 ，则 接受 作为输入。
Notice that a nondeterministic machine accepts an input even though it may have many nonhalting computations on this input - as long as at least one halting computation exists.
（或者更人话一点？） → TM accepts string if is in , and either rejects or does not halt if is not in
Nondeterministic TM M decides a Language L
Lecture 2 decides if the following holds for all
- There is a natural number , depending on and , such that there is no configuration satisfying
- if and only if for some .
→ TM accepts string if is in , and rejects w if w is not in L.
(2) State the Church-Turing Thesis
Lecture 2 Algorithm = Turing Machine that halts on all inputs.
(3) Prove the following language is not recursively enumerable = { : either is not the encoding of a Turing machine, or it is the encoding “” of a Turing machine that does not halt on “” }.
Elements of Theory of Computation Assume that is recursively enumerable. This means there exists a Turing machine that can semidecides .
However, by definition of , if and only if does not accept input string
. But is supposed to semidecide , so if and only if accepts . The contradiction arises and the assumption is error. Therefore, is not recursively enumerable.
书里（
Lecture 4 由于之前证明过 是递归可枚举的，则若 是递归的，那么每一个递归可枚举语言也都是递归的 → 即 = { “”: Turing machine halts on input string } 也是递归的 → 转为证明 不是递归的
假设 是递归的，那么它的补集也是递归的：
= { : either is not the encoding of a Turing machine, or it is the encoding “” of a Turing machine that does not halt on “” }.
→ 转为之前的证明思路
(4) Show that is Turing reducible to ( is the emptiness testing problem for TMs).
Lecture 5 = “On input :
- If , reject.
- If , run on input and accept if does.”
Assume that TM decides . Construct TM that decides as follows.
= “On input , an encoding of a TM and a string w:
- Use the description of and to construct the TM just described.
- Run on input .
- If R accepts, reject; if R rejects, accept.”
If were a decider for , would be a decider for . A decider for cannot exist, so we know that must be undecidable.