... equation¹

Like $10x^2 y + 10 z^3 + 7 x y^2 = 5$

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... states/configurations²

Logical level, not physical level

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 1s.³

That is what a state means.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... intuition⁴

In Physics, we don't know whether a machine has finite or infinite states. Though in implementation, a machine seems to have only finite states, but the fact that such a model even cannot ``count'' is ridiculous. So we reject the assumption not because the physical fact, but our intuition.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... sense⁵

this means, at any time, the machine doesn't know about ``all'' the information on the tape, but only the grid under its ``head''

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... be⁶

Wenting has asked a question about how is Computational System defined, and the answer seems to be: by our intuition...

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Machine⁷

Since Turing Machines can be encoded into binary strings, Turing Machines are enumerable.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... input.⁸

Inputs are also enumerable, but not nessesarily so.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... program.⁹

This does not rely on the theorem 2.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... computable.¹⁰

This relies on the theorem 2.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...#tex2html_wrap_inline1734#
¹¹

Read as ``$A$ is reducible to $B$''

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...#tex2html_wrap_inline1744#
¹²

This definition is confusing. In the textbook we learned, the definition of reduction is introduced by defining Oracle first. Of course, we don't have any code for an Oracle.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...#tex2html_wrap_inline1840#
¹³

depends on the specification of this Turing Machine.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...#tex2html_wrap_inline1846#
¹⁴

Used to extend or shrink the tape by managing spaces on the right end of the tape

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...#tex2html_wrap_inline2006#
¹⁵

$w$ is a computation history for $P$ and $I$ that shows that $P$ halts.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...#tex2html_wrap_inline2109#
¹⁶

That is, for any assignment $A$, $\Phi$ is true.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....¹⁷

$\exists$ cuicuit such that ...

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....¹⁸

$\exists$ matching

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....¹⁹

$\forall$ A, A doesn't make F true.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.