Infinite Computable
Not a new concept
What does infinite mean?
• The concept of infinity exists in our minds
• Does infinity actually exist?
• What does actually mean?
Is it a physical embodiment?
Between any two locations in space there is a third location? Or after every moment in time there is a next moment?
Cogito
• As a concept, no doubt it (infinity) exists
This is why it was given a name in the first place
• The same applies for: circle
straight line
Even a point
Almost everything
Can computers handle infinity?
• What do you mean by handle?
• What do you mean by computers?
• Alright, computers are Turing Machines
Can Turing Machines handle infinity?
• Still,whatdoyoumeanbyhandle?
• Do you mean save (encode) the whole set in the TM’s
memory?
• Well,theyhaveinfinitetapes.
Can a PHYSICAL computer handle ∞?
Can a physical computer handle an infinite set?
• If you mean save all of it, then according the physics we know so far, NO
• We don’t need to save a whole set
• Computability is about answering membership questions
Example
• The set of numbers divisible by 5 exists as a concept
• You can write a program, which can work for any given natural input,
to tell us if the given number is divisible by 5 or not.
Simply, look at the first digit from the right and check if it is 0 or 5.
Did we forget something?
• What does it mean to be given a number
• What if the number is too large to be saved as an input • Might take forever to find where it starts
TM’s are the best
• Tell me about a better way to talk about computers with arbitrary capacity
• TM’s for physical computers, are like the Circle for the sun
• The first is an ideal concept which smoothens a physical entity
• Or maybe the second is a rough physical manifestation of an ideal reality
Final words on infinite sets
• Handling infinity is problematic regardless of the whole computers talk
• Even problematic regardless of any physical realizations • Check The axiom of choice
Sets
• Set: Collection of objects (distinct)
Note that this is an informal definition. If interested in some formalism, and why it is needed, look into axiomatic set theory (would be a whole new course).
• Those objects inside a set can be sets themselves (sets of sets) • Fun fact: natural numbers can be interpreted as sets
Functions
• Formally, a function f from a set X to a set Y is the set of ordered pairs (𝑥, 𝑦) such that x is in X, y is in Y and every element in x is the first component for exactly one ordered pair.
• Informally, a function is a process, and what we mentioned above is called the graph of the function
• X above is called the domain
• A sequence (or string) is a function with domain N
Finite and Infinite Sets
• Informally, a set is finite if you can count it and finish
• Formally, S is finite if there exists a natural number n, and an injective
function 𝑓: 𝑆 → {0,1, … , 𝑛}
• A set is infinite if it is not finite.
Or equivalently: S is infinite if there is an injective function 𝑔: N → 𝑆
Cardinality
• Two sets are said to have the same cardinality (equinumerous) if there is a bijection between them
• The cardinality of a set A is denoted by |𝐴|
• A Cardinality is actually an equivalence class of the relation of equinumerosity
Comparing Cardinalities
• |𝐴| ≤ |𝐵| if there is an injection (injective function) from A to B.
• Such injection could be a bijection, in which case we have 𝐴 = |𝐵|
• For every set S, the set 𝑃(𝑆) (of all subsets of S) has a strictly larger cardinality than S. I.e. |𝑆| < |𝑃(𝑆)| (there is no bijection)
Some sets are more infinite than others
•N<𝑃N<𝑃𝑃N<⋯
• A set A is countable if |𝐴| ≤ |N| (so it can be finite or infinite)
• A set A is uncountable if it is not countable.
In other words, if there is an injection of the natural numbers into A,
but no injection of A into the natural numbers. • Clearly uncountable is always infinite
The Continuum Hypothesis (just for fun)
•Canyoufindaset|𝐴|suchthat N < 𝐴 < 𝑃 N ? Ans: Yes and No
• Don’t mix computable, countable, uncountable, not computable
• Uncomputable = non-computable = not computable
• In the realm of computability, WLOG, we will only be dealing with countable sets (subsets of N)
• Recall, recursive functions and Turing machines deal with objects which can be coded as natural numbers
Back to where we finished last lecture
• We saw how we can give programs numbers (e.g. via Gödel numbering)
• We let 𝑃 denote the 𝑒𝑡h Turing program, and 𝜑 the corresponding 𝑒𝑒
partial computable function (in one variable)
• This implies that the set of all Turing Machines is countably infinite (infinite and countable)
The Universal Turing Machine
• There exists a TM 𝑈 which if given input (𝑒, 𝑥) it runs the eth TM with input 𝑥.
• Follows from CT
Infinite Computable
• A set is infinite computable if it is infinite and also computable • Red V neck T-shirt: A T-shirt which is red and has a V neck
Infinite Computable is Diophantine
• Indeed, Diophantine = C.E.
• Computable >> C.E.
• Thus, Computable >> Diophantine
• Infinite & Computable >> Diophantine
The empty set is computable
• It is finite and every finite set is computable (why?)
• Or more directly: the characteristic function of the empty set is the zero function which is in computable (even more, it is initial in PRIM)
Prove that: If A is computable, then it is c.e. (decidable >> listable)
Proof1:
𝐼 is computable (given). 𝐴
Recall: a set is c.e. if it is empty or is the range of a computable function. If A is empty, then it is c.e. (implication holds by definition).
Assume 𝐴 ≠ ∅. We want to find a computable function f such that 𝑟𝑎𝑛𝑔𝑒𝑓 =𝐴.
Since A is non-empty, there must be some 𝑎 ∈ 𝐴. Fix such an 𝑎. Let 𝑓 be the function defined as follows
𝑥 𝑖𝑓𝐼 𝑥 =1 𝑓𝑥=ቊ 𝐴
𝑎 𝑖𝑓𝐼 𝑥 =0 𝐴
Proof2:
We describe a program that enumerates A which by CT can be mimicked by a Turing machine.
i=0
c=0
While i==0:
if 𝐼 𝑐 = 1: #this runs a sub-program 𝐴
print(c) c = c+1
C.E. but not Computable (FINALLY)
Let 𝐾 = {𝑥: 𝜑𝑥(𝑥) ↓}
• Show that K is c.e. (Think)
• Show that K is NOT computable
• Assume towards a contradiction that K is computable. • Consider the following function:
𝑓 𝑥 =ቊ𝑢𝑛𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑖𝑓𝑥∈𝐾 0 𝑜.𝑤
This f is partial computable because it can be mimicked by a TM: 1. we can computably decide if x is in K or not.
2. If x is in K, go in an infinite loop
3. If x is not in K, output 0
• But then, f must have a Gödel number, say e. I.e. 𝑓 = 𝜑𝑒 • If 𝑒 ∈ 𝐾, then
𝜑𝑒 𝑒 =𝑓 𝑒 ↑i.e.𝑒∉𝐾(contradiction)
•If 𝑒∉𝐾,then
𝜑𝑒 𝑒 =𝑓 𝑒 =0i.e.𝜑𝑒 𝑒 ↓i.e.𝑒∈𝐾(contradiction)
ഥ What can you say about 𝐾?
Remarks
• There are uncountably many non-computable subsets of N
• This is because there are only countably many computable sets
(why?)
• The same applies to the bigger class of c.e. sets. There are only countably many such sets.
• This means that the class of c.e. sets is very small
More about c.e. sets
• We defined a set to be c.e. if it is empty or the range of a computable function
• One can also show it is the range of a partial computable function (exercise)
• One can also show it is the domain of a partial computable function • All are equivalent definitions
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𝑑𝑜𝑚 𝜑 =𝐴
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 if 𝑅 (𝑥, 𝑒) then you 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 𝜑 (𝑥) ↓ 𝑒
• Recall that 𝜑𝑒(𝑎) ↓ means that the partial computable function 𝜑𝑒 is defined at a, or equivalently, that the program 𝑃 halts when given a
as an input
• Consider now the following new notation 𝜑𝑒,𝑠 𝑥 ↓. It means the
computation halts within s steps (or stages) •𝜑𝑒(𝑥)↓iff∃𝑠𝜑𝑒,𝑠 𝑥 ↓
𝑒
• Note that, for any fixed s the relation 𝑒, 𝑥 : 𝜑𝑒,𝑠 𝑥 ↓ is computable unlike{ 𝑒,𝑥 :𝜑𝑒(𝑥)↓}aswementionedbefore
• Actually, the following ternary relation is computable { 𝑒,𝑠,𝑥 :𝜑𝑒,𝑠(𝑥)↓}
• In general, 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
•AsetAisΣ0 meansthatitiseitheremptyortherangeofaΣ0 function f 2 1
• More clearly, f can be computed with a program which has access to, e.g., the set K we described earlier
• Such program is given the knowledge of the indicator function of K