Write some Software

Write a well-structured program that: 1. reads all quadruples of an input TM and a set of input strings (intended for this input TM) and prints out both input TM and all input strings. 2. decides whether or not each input string is to be accepted by the input TM and outputs one of three possible outcomes: a. YES (accepted) b. NO (rejected) c. UNKNOWN (not sure whether accepted or rejected) Simplifying Conventions: In general, as the question of whether or not a given TM accepts a given input string is UNDECIDABLE (or UNSOLVABLE) as you know by now, we cannot definitely decide YES or NO in some cases. So in order to simplify your programming efforts, we can adopt a convenient convention in deciding the outcomes for this given program as follows: 1. YES case: If your program (which is a simulator) finds out that the input TM is about to stop (why? Because the TM has no quadruple instruction that matches the combination of the Current state and the Current tape symbol, as you should know). And this case is DEFINITE. 2. NO case: For this particular input TM program, we notice that there are some quadruples that guarantee that the input TM does not stop because the instruction itself is an infinite loop: These quadruples include: N5: Q4 B B Q4 N12: Q6 2 2 Q6 N13: Q6 B B Q6 N15: Q8 B B Q8 N22: Qa 1 1 Qa N23: Qa B B Qa // You should make sure there are no // others yourself 3. UNKNOWN case: This case is for any input string for which your program does not decide that it is YES case nor NO case, that is, neither YES case nor NO case. Note that, in general, this conclusion is indefinite unlike the first two conclusions of YES and NO. But that is OK as this is just an exercise for fun. 4. Also, note that we assume the following Initial I.D. for any TM: ...BBBQ1BXBBB... where X is an input string and Q1 is the initial state. Inputs to be used: Use the following TM (29 quads) and seven strings for inputs: A. Input TM 1. Move to the rightmost input symbol. N1: Q1 B R Q1 //Reject the empty input string N2: Q1 1 B Q2 //Leftmost=1 N3: Q1 2 B Q3 //Leftmost=2 N4: Q2 B R Q4 N5: Q4 B B Q4 //Reject odd length. N6: Q4 1 R Q5 //Get to rightmost symbol (1 or 2) N7: Q4 2 R Q5 / /Same N8: Q5 1 R Q5 / /Same N9: Q5 2 R Q5 //Same N10: Q5 B L Q6 //End of input string rightend, so go left. N11: Q6 1 B Q7 //Matching rightmost symbol (1) N12: Q6 2 2 Q6 //Unmatching, so reject N13: Q6 B B Q6 //Impossible but just in case (Reject) N14: Q3 B R Q8 //Start to move right looking for matching 2. N15: Q8 B B Q8 //Odd length (Reject) N16: Q8 1 R Q9 N17: Q8 2 R Q9 N18: Q9 1 R Q9 N19: Q9 2 R Q9 N20: Q9 B L Qa //End of rightend, so move left. N21: Qa 2 B Q7 //Matching rightmost symbol (2) N22: Qa 1 1 Qa //Unmatching, so reject. N23: Qa B B Qa //Impossible, but just in case. 2. Move to leftmost input symbol. N24: Q7 B L Qb //Qb is the only accepting state //when no input symbol remains. N25: Qb 1 L Qc N26: Qb 2 L Qc N27: Qc 1 L Qc N28: Qc 2 L Qc N29: Qc B R Q1 //Just passed the leftmost symbol, so //move right to get to it. //At Q1, the current symbol must be 1 or 2. B. Seven input strings: 1212 1221 122221 221221 12122121 221122 2211122