Description

Assignment2

1. Short Answer Questions. (4pts)
1） What is the basic unit of TM model? Please briefly describe what each unit does. （2pts）
2） In single computation step, what needs to be done？（1pts）
3） How many possible result cases of a computation process of a TM? Please list them. （1pts）
2. True or False （2pts, 1pts per question）
a）If the computation process of the TM never halting, there are infinite states in its set of states Q.
b) Logic is the father/mother of Computer Science.

3. Consider Turing machine M1 with the following state diagram and answer the questions. （4pts)

Note: The reject state and the transitions going to the reject state are not shown in the state diagram. The transitions occur implicitly whenever a state lacks an outgoing transition for a particular symbol. For completeness, we say that the head moves right in each of these transitions to the reject state.

1) If the start configuration is qa10101011, Turing machine M1 will enter ___. (accept state, reject state, never halting). If M1 enter accept state or reject state, what is the halting configuration? (2pts)
2) If the start configuration is qa01010101, Turing machine M1 will enter ___. (accept state, reject state, never halting). If M1 enter accept state or reject state, what is the halting configuration? (2pts)