CS计算机代考程序代写 Oracle Machines

Oracle Machines
Beyond C.E. sets

Co-hosted by Paul

From before
• C.e. sets are those a computer can list
• Computable: a computer can list them, and can also list their
complements
• The set 𝐾 = {𝑥: 𝜑𝑥(𝑥) ↓} is c.e. but not computable

• 𝐾 (the complement of 𝐾) is not c.e.

About c.e. sets
• We first defined a set to be c.e. if (means iff) it is empty or the range of a computable function
• We showed that a set is c.e. iff it is the range of a partial computable function
• We also showed that a set is c.e. iff it is the domain of a partial computable function

Proof:
Let A be a c.e. set
If A is empty, then A is the domain of the empty function given by the program which doesn’t halt on any input
If A is not empty, then it is the range of a computable function, say 𝐴 = {𝑓 0 ,𝑓 1 ,𝑓 2 ,…}.
Let𝜑 𝑥 =𝜇𝑦[𝑓 𝑦 =𝑥].Then𝑑𝑜𝑚 𝜑 =𝐴

Let’s analyze the last definition of C.E.
• A is c.e. iff it is the domain of a p.c. function f.
• Given any x, if x is in A, then the 𝑓(𝑥) ↓, and if x is not in A, then
𝑓(𝑥) ↑
• So basically, we have a program that will confirm that YES if x is in A, and otherwise the program tells us nothing

Notation
• The domain of 𝜑 is denoted by 𝑊 𝑒𝑒
• 𝑊 is the e-th c.e. set 𝑒

C.E. and ∃
• There is a strong relationship between c.e. and the existential
quantifier •IfAisc.e.,thenforsomee,xisinAiff∃𝑠𝜑𝑒,𝑠 𝑥 ↓
Where, roughly, 𝜑𝑒,𝑠 𝑥 ↓ means that the computation halts within s steps (or stages).
• Note that { 𝑒,𝑠,𝑥 :𝜑𝑒,𝑠 𝑥 ↓} can be regarded as a relation 𝑅 𝑥1,𝑥2,𝑥3

Computable Relations
• Recall, a binary relation over sets X, Y is a subset of the Cartesian product 𝑋×𝑌
• More generally, an n-ary relation over sets 𝑋 , … , 𝑋 is a subset of 1𝑛
𝑋 ×⋯×𝑋 1𝑛
• Ann-aryrelationonNisoneforwhich𝑋 =⋯=𝑋 =N 1𝑛
• A relation on N is computable if it is computable as a set • Wesayarelationisc.e.ifitisc.e.asaset.

Example
• 𝑅={ 𝑥,𝑦,𝑧 ∈N3:𝑥<𝑦𝑎𝑛𝑑𝑧=2𝑥} We have 𝑅 1,2,2 , 𝑅 0,3,0 , 𝑅(10,11,20) But ¬𝑅 0,2,2 , ¬𝑅 0,0,0 , ¬𝑅(10,11,11) Here ¬ means negation • 𝑅 is clearly computable. There’s a program which when given any tuple (𝑎, 𝑏, 𝑐) it can decide if 𝑅 𝑎,𝑏,𝑐 or ¬𝑅 𝑎,𝑏,𝑐 • Note that we can regard relations as Boolean valued functions •𝑅 ={(𝑥,𝑒)∈N2: 𝜑 (𝑥)↓} 2𝑒 Not computable (why?) But it is c.e. because, for any given values a,b, if 𝑅 (𝑎, 𝑏) then we can confirm that computably 2 Special Cases • Note that a function is a binary relation • A non-empty subset of X is a unary (1-ary) relation on X. • There are 0-ary relations (TRUE and FALSE) • There is the empty relation ∅ which is the same as FALSE (holds for nothing) Deeper analysis of 𝜑 (𝑥) ↓ 𝑒 •Weassumes>xands>ewhenwewrite𝜑𝑒,𝑠 𝑥 ↓
• When we write 𝜑𝑒,𝑠 𝑥 ↓= 𝑦 , we assume that s is greater than x,e,y
• Recall that the following ternary relation is computable { 𝑒,𝑠,𝑥 :𝜑𝑒,𝑠(𝑥)↓}

One can prove that:
A relation 𝑅(𝑥, 𝑦) is c.e. iff there exists a computable relation
𝐶(𝑎, 𝑥, 𝑦)
such that for all x,y
𝑅𝑥,𝑦 ⟺∃𝑎𝐶𝑎,𝑥,𝑦

The Arithmetical Hierarchy
• We use Σ0 to denote the class of relations (formulas) obtained as 1
∃𝑎ത 𝐶 𝑎ത, 𝑥ҧ using some computable relation 𝐶
• Π0 denotes the class of relations (formulas) obtained as ∀𝑎ത 𝐶 𝑎ത, 𝑥ҧ
1
using some computable relation 𝐶
• Note that if a set is Σ0 then its complement is Π0 , and vice versa 11

Going higher
• Π0 denotes the class of relations (formulas) obtained as 2തത
∀𝑎ത∃𝑏 𝐶 𝑎ത, 𝑏, 𝑥ҧ using some computable relation 𝐶 Or equivalently ∀𝑎ത 𝐷 𝑎ത, 𝑥ҧ for some Σ0 relation D
• Σ0 denotes the class of relations (formulas) obtained as
2തത
∃𝑎ത∀𝑏 𝐶 𝑎ത, 𝑏, 𝑥ҧ using some computable relation 𝐶
1

In general
• Π0 denotes the class of relations (formulas) obtained as 𝑛+1 0
∀𝑎ത 𝐷 𝑎ത, 𝑥ҧ for some Σ𝑛 relation D
• Σ0 denotes the class of relations (formulas) obtained as ∃𝑎ത 𝐷 𝑎ത, 𝑥ҧ
𝑛+1 0
for some Π𝑛 relation D
• Note that, for all n, Σ0 ∪ Π0 ⊊ Σ0 ∩ Π0
𝑛 𝑛 𝑛+1 𝑛+1

• Recall we mentioned that
A relation 𝑅(𝑥, 𝑦) is c.e. iff there exists a computable relation 𝐶(𝑎, 𝑥, 𝑦) such that for all x,y
𝑅𝑥,𝑦 ⟺∃𝑎𝐶𝑎,𝑥,𝑦
• This means that C.E. = Σ0 1
• BTW, Computable = Σ0 = Π0 00

The Normal Form Theorem for C.E. Sets
• The following are equivalent: • A is c.e.
• A is Σ0 1
•A=𝑊 forsome𝑒∈N 𝑒

Relative Computability
• We have just seen that C.E. = Σ0 1
• How about Σ0 ? Or more generally, Σ0 ? 2 𝑛+1
• Are they c.e. in some sense w.r.t. some higher level?
• Indeed, it is all about the computable function which enumerates the set

Oracle Machines and Relative Computability
• Imagine a function which is computable but only after giving it certain knowledge
• Imagine its program which allows using the indicator function of some set A (not necessarily computable)
• Such a function is said to be (relatively) computable from A

Turing Reducibility
•AsetSissaidtobeTuringreducibletoasetB(𝑆 ≤𝑇 𝐵)ifthe characteristic function of S is computable from B.
•If𝑆 ≤𝑇 𝐵and𝑆 ≥𝑇 𝐵,thenwewrite𝑆 ≡𝑇 𝐵andsaytheyare Turing equivalent
• ≤𝑇 is a partial order, and ≡𝑇 is an equivalence relation

Turing Degrees
• The equivalence classes corresponding to ≡𝑇 are called the Turing degrees (often denoted by bold lowercase a, b, c, ..)
• They are also known as degrees of unsolvability
• All computable sets have the same Turing degree (why?)

Structure of the set of Turing Degrees
• Partially ordered but not linearly ordered (there are incomparable degrees)
• There is a smallest Turing degree which is the Turing degree of the empty set (which is also the Turing degree of any computable set)

Notation
• 𝑃𝐴,𝛟𝐴,𝑊𝐴 𝑒𝑒𝑒
Program with oracle A, p.c. function with oracle A, A-c.e. set

How to get higher degrees? (the Jump operator)
• Given a set A, consider the halting set with respect to A:
′𝐴𝐴𝐴
𝐴 =𝐾 = 𝑥:𝛟 𝑥 ↓ ={𝑥:𝑥∈𝑊 } 𝑥𝑥
′ • ThissetiscalledthejumpofAandwehavethat𝐴<𝑇 𝐴 • ∅′ = 𝐾 • 𝐴 ≡𝑇 𝐵 implies 𝐴′ ≡𝑇 𝐵′ • 𝐴′ is 𝐴-c.e. but not 𝐴-computable Iterating the jump • ∅′′, ∅′′′, ... • ∅(2) = ∅′′ • ∅(𝑛) • deg ∅ = 𝟎 • deg 𝐴 ′ is defined asdeg 𝐴′ • deg ∅(𝑛) = 𝟎(𝑛) C.E./ Co-c.e. Computable level Other Reducibilities • Note that Turing reducibility does not distinguish a set from its complement (for any set 𝐴, 𝐴 ≡𝑇 𝐴ҧ) • But clearly both sets can be very different in terms of computability ഥ properties. Example: 𝐾 and 𝐾 • Similar properties can be maintained by stronger reducibilities m-reducibility (many-one reducibility) • 𝐴 ≤𝑚 𝐵 (𝐴 is m-reducible to 𝐵) if there exists a computable function 𝑓 such that: for every 𝑥 ∈ N, 𝑥 ∈ 𝐴 iff 𝑓(𝑥) ∈ 𝐵