[ITOC-ch6] ADVANCED TOPICS IN COMPUTABILITY THEORY

[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 ] $