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 𝑓(𝑥) ∈ 𝐵