CS计算机代考程序代写 Infinite Computable

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