Points | Grade |
---|---|
90+ | A |
80-89 | A- |
70-79 | B+ |
60-69 | B |
50-59 | B- |
40-49 | C+ |
Note that your grade is based on the total number of points you earn. For example, one could achieve an "A" by attempting 90 points worth of problems and solving them perfectly, or by attempting 180 points worth of problems and obtaining 1/2 credit on each, etc.
Your solutions and/or programs will be due no later than the date of the scheduled final exam for this course, Fri Dec 19.
3 q1 q2 q3 2 a b q2 q1 q3 q3 q2 q1 q1 1 q2Line 1 specifies the number of states, and Line 2 specifies states. Line 3 specifies the size of the alphabet, and Line 4 specifies the alphabet. Lines 5-7 give the transition function, each row corresponding to a state (in order) and each column corresponding to a symbol from the alphabet (in order). Line 8 specifies the start state. Line 9 specifies the number of final states, and Line 10 specifies the final states.
You need not use this encoding, but you must specify (and use) some consistent encoding.
You must submit your program code and provide a demo.
Hint: You may assume the following mathematical fact (Dirichlet's Theorem). First, however, we'll need a bit of background.
Two integers a and b are said to be relatively prime if they share no factors in common. For example, 15 and 26 are relatively prime since the prime factors of 15 are {3, 5} and the prime factors of 26 are {2, 13}; however, 15 and 25 are not relatively prime since they share the factor 5 in common.
Given two numbers a and b, the arithmetic
progression
Hint: You may wish to make use of the following facts: The sum of an odd number of odd integers is odd, and the sum of an even number of odd integers is even. (If you use these facts, you should prove them as part of your solution.)
You must submit your program code and provide a demo on a "reasonable" Turing Machine, such as the one given in Figure 3.4.
Hint: Reduce from ATM. Assume, without loss of generality, that a Turing machine which accepts the empty language does not have property P. (If not, consider the complement of property P. If the complement of property P is undecidable, then so is P since the decidable and undecidable languages are closed under complement.)
Given an instance <M,w> of ATM, your task is to construct a TM M' so that M' has property P if and only if M accepts w.