A Turing-recognizable language consisting of descriptions of Turing machines

Problem:

Let $ A $ be a Turing-recognizable language consisting of descriptions of Turing machines, $ \{(M_1 ), (M_2), \cdots \}$, where every $ M_i $ is a decider. Prove that some decidable language $ D $ is not decided by any decider $ M_i $ whose description appears in $ A $.
(Hint: You may find it helpful to consider an enumerator for $ A $.)

Short answer: 

We can adopt the diagonalization argument to produce a decidable language that is not accepted by any of the $ M_i $.

Proof:

Consider the language $ D $ decided by the following Turing machine

Reject any input that is not a binary number.
Enumerate the ith Turing machine, where $ i $ is the input string.
If $ M_i $ accept the input string, reject it, otherwise accept it.

Apparently this is a Turing machine, and it is not accepted by any of the $ M_i $ (there is always a string $ i $ where $ M_i $ does not agree with $ D $)

Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.

Problem:

Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.

Proof idea:

The number of Boolean function is huge (i.e. exponential exponential) but the number of circuit you can make out of polynomial number of gates is smaller than that.

Proof:

The number of Boolean functions of n input can be counted by listing the output of the Boolean function output starting from

00000..000 = 0
00000..001 = 0
...

There are $ 2^n $ rows, therefore every unique bit string of length $ 2^n $ represents an unique Boolean function, so we have $ 2^{2^n} $ Boolean functions.

On the other hand, if we have a polynomial number of gates, they could be arranged in anyway, the number of circuits could be at most $ (cn^s)! < 2^{cn^s} < 2^{2^n} $, therefore, most of the circuits do require more than polynomial number of gates.

Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.

Problem:

Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.

Short proof: 

If such an infinite subset exists, we can compress those strings using a Turing enumerator.

Proof:

If such an infinite subset exists, we build an enumerator of them. By the recursion theorem, we can build a Turing machine that enumerate the strings that infinite subset and stop on the first string that is larger than the representation of itself.

Such a machine must eventually halt because of the set must have a string with length larger than this finite machine.

Show that NP is closed under union and concatenation

Problem:

Show that NP is closed under union and concatenation

Short answer: 

We can build non-deterministic Turing machine to solve the union language and the concatenation language

Proof:

Assume language X and language Y are in NP, we wanted to show X union Y is in NP

Because X and Y are in NP, there exists non-deterministic Turing machine X and non-deterministic Turing machine Y that verifies X and Y, respectively.

Rename the states in Y so that it does not have the same name as in X.

Build a new non-deterministic Turing machine U as follow:

Create a new start state, for each input symbol, it write the same symbol back to the tape, and non-deterministically go to the start state of X or the start state of Y. Take the union of state and transition function from both X and Y, that is a non-deterministic Turing machine U.

For any string in X, non-deterministic Turing machine U can take a non-deterministic jump to the start state of X, and follow the non-deterministic Turing machine X to finally get accepted.
For any string in Y, non-deterministic Turing machine U can take a non-deterministic jump to the start state of Y, and follow the non-deterministic Turing machine Y to finally get accepted.
For any string that is neither in X nor in Y, non-deterministic jump to either X or Y cannot lead to acceptance.

Therefore we showed the non-deterministic Turing machine U precisely accept X union Y.

Assume language X and language Y are in NP, we wanted to show X concatenate Y is in NP

Because X and Y are in NP, there exists non-deterministic Turing machine X and non-deterministic Turing machine Y that verifies X and Y, respectively.

Rename the states in Y so that it does not have the same name as in X.

Build a new non-deterministic Turing machine C as follow:

For each final state in X, for each input symbol, write the same symbol back to the tape and jump to the start state of Y, and make it non-final.

For any string in X concatenate Y, it can follow the non-deterministic Turing machine X to go to final state of the original non-deterministic Turing machine X, jump to start state of Y, and then follow it to the final state of Y.

For any string, it cannot possibly go to a final state without going through a original final state of X. (All path to final state goes through it)

But if it goes through to final state through a original final state of X, the string could be split into two pieces where a prefix is in X and a suffix is in Y, that means the string has to be in X concatenate Y.
The contrapositive of this show if a string is not in X concatenate Y, it is not accepted.

Therefore we showed the non-deterministic Turing machine C precisely accept X concatenate Y.

Is NP countable?

Problem: 

Is NP countable?

Short answer: 

yes

Proof:

For each problem in NP - there exists a non-deterministic Turing machine as verifier.
As we can encode non-deterministic Turing machine as finite binary string, the set of non-deterministic Turing machine is countable, therefore the set NP is also countable.

Problem 1.32

The key to this problem is to construct a DFA that can recognize that reverse sum language. With that, we can invoke problem 1.31 to show the sum language is also regular.

The proposed DFA has 3 states, the first state is the start state and represents the last digit has no carry, and the second state is the with carry state represents the last digit has a carry. The third state is the error state. The first state is also the final state.

To simplify discussion, any unrecognized alphabet in a state go to the error state, and it stuck forever there by having all alphabets points towards it.

Now in the start state, we have these transitions:

$ \left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right) $ , $ \left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 1\end{matrix}\right) $ goes to start state.
$ \left(\begin{matrix} 1 \\ 1 \\ 0\end{matrix}\right) $ goes to carry state.

In the carry state, we have these transitions:

$ \left(\begin{matrix} 0 \\ 0 \\ 1\end{matrix}\right) $ goes to the start state
$ \left(\begin{matrix} 0 \\ 1 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 1 \\ 1\end{matrix}\right) $ does to carry state.

That's it, we completed the description for the DFA that can recognize the reverse sum language. 

That shows the reverse sum language is regular. By problem 1.31, the sum language is also regular!

Q.E.D.

Problem 1.31

Finally, we really doing something about the theory of computation!

To show the reverse $ L^R$ of a regular language L is also regular. We will construct a non-deterministic finite automata (NFA) for the language. Since L is a regular language, it has a deterministic finite automata (DFA).

The idea is simply to run the DFA backward. But there is one complication - a DFA could have multiple final states. So we simply extend the original DFA to NFA by joining merging all the final states to a single final state with epsilon transition.

Then we reverse all transitions to go backward, using the merged final state as start state, and the original start state as the final state, we obtain a NFA for the reverse language.

To show the constructed NFA actually works. Consider a string w in L, there exist a path from the original start state to the merged end state. So there exist a reverse path in the constructed NFA as well. The transitions are exactly the same as it was, only in reversed order, so the reverse string is recognized.

For a string that is NOT in w, however, the original DFA will lead to a non-final state, so we cannot take the epsilon path to the merged final state. Note that before exhausting all input symbols, it might reach the final state and took the epsilon path before. But since the merged final state does not consume any symbol, the path cannot extend there.

Now assume somehow the reverse is accepted, so there exists a path from the merged final state back to the original start state with symbols reversed, but then it would mean a path exist from the original start state to the merged final state by reversing it, which we already proved doesn't exist. The contradiction shows the reverse cannot be accepted.

Together we show our constructed NFA accepts precisely the reverse language. So the reverse language is regular.