Let M1 be a TM that decides L1 and let M2 be a TM that decides L2. The following TM M decides L = L1 intersection L2: Let M = "on input string w:Let's prove that the Turing machine M above decides the language L1 intersection L2. M accepts w iff both M1 and M2 accept w iff w belongs to L1 AND w belongs to L2 iff w belongs to L1 intersection L2. M rejects w iff either M1 or M2 or both reject w iff w doesn't belong to L1 and/or w doesn't belong to L2 iff w doesn't belong to L1 intersection L2. Note that the machine M is guaranteed to halt, since M1 and M2 are deciders and so guaranteed to halt on all inputs.
- Run M1 and M2 in parallel (or one after the other).
- If both M1 and M2 accept w, then accept w.
- If either one rejects w, then reject w.
Let S1 be a TM that semi-decides L1 and let S2 be a TM that semi-decides L2. The following TM S semi-decides L = L1 intersection L2: Let S = "on input string w:Let's show that S semi-decides L = L1 intersection L2: S accepts w iff both S1 and S2 accept w iff w belongs to L1 AND w belongs to L2 iff w belongs to L1 intersection L2. Note that the machine S may loop on input w if both S1 and S2 loop on w (tough we could have chosen to let S loop if one of these machines loops on w and the other one rejects w and still S would be semi-decider for L). However, if w belongs to L1 intersection L2, then both S1 and S2 halt and accept w and so S is guaranteed to halt accepting input w.
- Run S1 and S2 in parallel.
- If both S1 and S2 accept w, then accept w.
- If either one rejects w, then reject w.
- (Note that if both S1 and S2 "loop" on input w, then S will have to loop with them.)
Here are two possible solutions to this problem: Solution 1: Define pw2 by inductive definition as follows: pw2(0) = 1 pw2(succ(n)) = mult(succ(succ(0)),pw2(n)) Since mult and succ are primitive recursive as proven in class (and handout), and inductive definition preserves the property of being primitive recursive, pw2 is primitive recursive. Solution 2: Define pw2 by inductive definition as follows: pw2(n) = exp(succ(succ(0)),n) where exp(x,y) is the exponentiation function x^{y} proven to be primitive recursive in class (and handout). Since pw2 is defined as the composition of succ and exp then pw2 is primitive recursive.
(Hint: If you wish, you can use the fact that bounded minimization preserves the property of being primitive recursive. If you wish, you can disregard this hint.)
Here are two possible solutions to this problem: Solution 1: Define log2 using bounded minimization as follows: log2(n) = mu^{n} z [ greater_than(pw2(succ(z)), n) ] where: "mu^{n} z" means "the least number z less than or equal to n" greater_than(x,y) = mult(geq(x,y), not(equal(x,y))) Since succ, mult, not, equal were shown to be primitive recursive in class and/or handout and/or hw1, pw2 was shown to be prim. rec. above and bounded minimization preserves the property of being primitive recursive, then log2 is primitive recursive. Solution 1: Define log2 using a helper function helper_log2: log2(n) = helper_log2(n,n) The helper function is defined using inductive definition as follows: helper_log2(n,0) = 0 / | k, if greater_than(pw2(succ(k)),n)=1 helper_log2(n,succ(k)) = | | helper_log2(n,k), if greater_than(pw2(succ(k)),n)=0 \ Since pw2 and greater_than were shown to be prim. rec. above and definition by cases (see proof below) and inductive definition preserve the property of being primitive recursive, then helper_log2 is primitive recursive and so is log2.
/ | g(k,m,n), if p(k,m,n)=1 f(k,m,n) := | | h(k,m,n), if p(k,m,n)=0 \where g and h are functions from NxNxN -> N, and p is a function from NxNxN -> {0,1}. Prove that if g, h, and p are all primitive recursive functions, then f as defined above is also primitive recursive.
Solution: f(k,m,n) = plus(mult(g(k,m,n),p(k,m,n)), mult(h(k,m,n),not(p(k,m,n)))) The explanation below is adapted from John Shutt's solutions to HW2, D term 2002. f is constructed by composition from previously shown primitive recursive functions mult, plus, and not (from handout and class and hw2), and functions g, h, and p that are primitive recursive by supposition. So f is primitive recursive. Ifp(k,m,n)=0
, thenf(k,m,n) = 0*g(k,m,n) + 1*h(k,m,n) = h(k,m,n)
. Ifp(k,m,n)=1
, thenf(k,m,n) = 1*g(k,m,n) + 0*h(k,m,n) = g(k,m,n)
. Sof
is the intended function.
is decidable.
Solution 1 Proof Idea: The idea of the proof below is the following: L(R) is a subset of L(S) iff L(R) intersected with the complement of L(S), L(S)^{C} is the empty set. We'll use Theorem 4.4 (or its equivalent for regular expressions) to prove that the condition "L(R) intersection L(S)^{C} = empty set" is decidable. Proof The following Turing machine N decides the language SUBSET_{rex}. "On input string x,
- Check that x encodes a pair < R,S > where R and S are regular expressions
If it does not, then reject x.
- Translate R into an equivalent DFA DR and S into an equivalent DFA DS using the procedure given in Theorem 1.28.
- Construct a DFA DS^{C} that accepts the language L(DS)^{C}.
- Construct a DFA D that is the intersection of DR with DS^{C}. That is, L(D) = L(DR) intersection L(DS^{C}).
- Now, run the Turing machine T from Theorem 4.4 (see p154) with input < D > to determine if L(D) is empty. If T accepts < D > (which means that L(D) is empty), then accept x. If T rejects < D > (which means that L(D) is NOT empty), then reject x."
Now we prove that the TM N decides the language SUBSET_{rex}.
by implementing a Turing machine that decides this language. As an illustration, note that "abaabbbab" and "b" belong to the language, but the following words do not: "aabbba", "abaaa", and "" (the empty word).
Solution: By Adam Elliot. Gamma={a,b,X,_,triangle} (_ is blank, triangle is start-of-tape symbol, X is the marker) 1. Make sure the input string is odd-length and contains only a and b: This approach uses a two-state procedure to search for the end of the word, oscillating between a reject and a "continue" state. So always moving right.... A. Read an a, b, or blank. If blank, reject. B. Read an a, b, or blank. If blank, continue on to 2. Otherwise, go back to A. 2. Now verify the middle character is a "b": Move the head back to the beginning. Move right until a non-marked character is found: If it's an "a": - Mark it with an X. - Scan right, until an X or blank is encountered, then move left. - If this is an X, then we didn't find a match, which means that "a" was the middle character. Reject. - Otherwise, mark with X, rewind, repeat. If it's a b: - Mark it with an X. - Scan right, until an X or blank is encountered, then move left. - If this is an X, then we just discovered the middle character is a b. Accept. - Otherwise, mark with X, rewind, repeat. Alternative Solution: Construct a non-deterministic Turing machine that non-deterministically chooses a b in the input (if no b is found the machine rejects the input word) and then checks that the strings in both sides of that b are of equal length.
See Adam's nice state diagram In that diagram "S" denotes the triangle at marks the Start of the tape.