Assignment 10

Automaton_Theory

陆一洲 5140309557

Problem 1

First, the formula can be written as $P_1P_2\cdots P_s$ where $P_i=x_{p_1}+\cdots+x_{p_k}+\bar x_{q_1}+\cdots+\bar x_{q_t}$.
Second, we guess $x_1$ to be either true or false. Then we can determine wheter some other $x_r$ which is related to $x_1$ is true or false. We denote the set of $x_r$ come from $x_1$ as $S_1$. Then we recursively guess the next $x_i$ which has not be determined, where we get $S_i$. etc.
Third, we can go over the whole formula in $\mathrm{O}(n)$ to find out whether our guess is valid. If it comes to some $x_i$ both to be true by $S_u$ and to be false by $S_v$, thenour guess is invalid.
Forth, for the worst case, i.e., there is no valid solution, we should run the Second and Third step for each $x_i$. It costs $\mathrm{O}(2\times n\times n)=\mathrm{O}(n^2)$ time, thus the complexity is in polynomial time.

Problem 2

1.
By diagonalization, we suppose that the name of the $i$th set $S_i$ is $n_i$ and $S'=\{n_i\mid n_i\notin S_i\}$. What we have to prove is that $S'$ is a recursive set.
Now we contruct a TM $M$ to accept $S'$. For any input $x_i$, we let $M$ simulate TM $x_i$ firstly. We can derive that it could be accepted or rejected by $x_i$ for the machine is recursive. So the machine accepts $S'$.
Thus, we cannot list names of all recursive sets if you require names to be Turing
machines that halt on all inputs.
2.
First, we list all the TM $M_1, M_2,\cdots$. We now construct a TM $M'$.
If $M_i$ halts on all inputs, then let $M'_i$ stimulate $M_i$ on all inputs. If the $M_i$ does not halt on all inputs, we can find one $x_j$, s.t. $M_i$ which $M'_i$ simulates halts on $x_1,x_2,\cdots,x_{j-1}$ and rejects others. Thus, $M'i$ halts on all inputs.
In all, we can list the names of all recursive sets if you allow names to be arbitrary
Turing machines.