## [ITOC-ch6] ADVANCED TOPICS IN COMPUTABILITY THEORY

### 6.1 THE RECURSION THEOREM

Making machines that reproduce themselves.

**SELF-REFERENCE**

Construct $ SELF $ prints out a copy of its own description.

**LEMMA 6.1**

define computable function $ q : Σ^ ∗\longrightarrow Σ ^ ∗ $

- w is any string, $ q(w) = < P_w > $
- $ P_w $ is a TM that prints out w and then halts.

$ SELF $

- 2 parts: $ A $ and $ B $, so $ < SELF > = < AB > $

RZ师兄的例子

1 2 3 4 5 6 7 8 9 | #python #Part A print <B> a = ['print "a=", a', 'for s in a: print s'] #B compute and print q(<B>) = <A> #这里q函数只是加上了a=而已 print "a=", a #B combine <B> (from the output of that A produce) for s in a: print s |

Extends the technique so that a program can **automatically** obtain its own description and then *go on to compute* with it

**Recursion theorem**

- First we have a T, than we can construct R
- Input w to R, R can obtain < R > and give < R > and w to T for further computation

$ A $ writes $ w < BT > $ , $ B $ writes $ < A > $ , together the resulting string $ < R, w > $ is on the tape, than passes control to T

**APPLICATIONS**

- computer virus
- Simpler proof of $ A_{TM} $ is undecidable (4.11显式构建了D出来)
- $ MIN_{TM} $ is not Turing-recognizable.
- For computable function $ t: Σ ^ ∗ → Σ^ ∗ $, there is a $ < F > = t( < F > ) $

### 6.2 DECIDABILITY OF LOGICAL THEORIES

**model**

- a tuple $ (U, P_1 , . . . , P_k ) $, where U is the universe ( possible variable values ) and $ P_1 $ through $ P_k $ are the relations assigned to symbols $ R_1 $ through $ R_k $.

language of a model

- use things only the model defined

**theory of M** $ Th(M) $

- the collection of true sentences in the language of that model

**6.12** $ Th(N , +) $ is decidable.

**6.13** $ Th(N , +, ×) $ is undecidable.

**6.16** Some true statement in $ Th(N , +, ×) $ is not provable.

(真假性客观存在但不可证明)

### 6.3 TURING REDUCIBILITY

Reducibility

- if A is reducible to B, and we find a solution to B, we can obtain a solution to A.

Mapping reducibility

- $ \exists f $ so $ w \in A \Longleftrightarrow f(w) \in B $

**Turing reducibility**

oracle for a language

- an external device that can report whether a string w is a member of the language

oracle Turing Machine

- TM that has the additional capability of querying an oracle.
- more powerful than TM
- Still cannot decide all languages

$ E_{TM} $ is decidable relative to $ A_{TM} $

- we can use the oracle of $ A_{TM} $ to decide $ E_{TM} $

### 6.4 A DEFINITION OF INFORMATION

*define information using computability theory.*

quantity of information

- the size of that object’s
**smallest**representation or description.

**MINIMAL LENGTH DESCRIPTIONS**

Select our language describing information

- describe a binary string x as $ < M > w $ while M is a TM and w is input
- locate the separation between $ < M > $ and $ w $
- One way to do so is to write each bit of $ < M > $ twice, writing 0 as 00 and 1 as 11, and then follow it with 01 to mark the separation point.

**6.24**: $ \exists c \forall x \ [ K(x) \le |x| + c ] $

**6.25**: $ \exists c \forall x \ [ K(xx) \le K(x) + c ] $

**6.26**: $ \exists c \forall x,y \ [ K(xy) \le 2K(x) + K(y) + c ] $