More about theorem 2

Physical discoveries, such as ``Universe is governed by the `loopy string theory' '', then there are these possibilities:

• Show loopy string allows you to build a machine that computes something that a Turing machine cannot compute.
• There may be obvious computational device ``loopy string theory Turing machine'', may be that a Turing can simulate a loopy string theory turing machine. This happens on quantum machanics.

Unfortunately, I forget what Professor Pruhs claimed more about this...In our textbook, quantum machanics was said to be not clear whether it is within Turing Machine's power.

Theorem 3   There is a decision problem that is not computable by Turing Machine.

Proof. Diagonalization. Every row represents a different Turing Machine⁷, while each column representing whether the Turing Machine halts on the given input.⁸ $\qedsymbol$

This actually says that the space of Problems is larger than the space of Turing Machines. Since Diagnoalization can be applied, it is easy to conclude that the space of Problems is inenumerable, while the space of Turing Machines is enumerably infinite.(This is my conclusion. It is not correct.)

Corollary 1   The Halting problem is not computable by a Turing Machine.

Corollary 2   The Halting problem is not computable by a Java program.⁹

Corollary 3   The halting is not computable.¹⁰

Definition 1   A problem is computable if for each input size there is a finite state machine that decides the inputs for that size.

See the following problem:

Input: String of length $n$.
Output: $1$ if Turing machine $n$ halts on input $n$, 0 otherwise.

According to the definition 1, the problem above will be computable. That is because for every input, if the answer should be yes, we can create a FA to simply ignore all its input and accept to solve it; otherwise, just create a FA to simply ignore all its input and reject. Thus, definition 1 is plausible but meaningless.