Computable Functions
Co-hosted by: Yousef Akiba
Turing Computability
• We learnt about Turing Machines
• A function is Turing computable if there is a TM that can compute it
• The Turing thesis (Faith): Every intuitively computable function is Turing computable
Gödel’s approach
• Recall that Gödel started with initial functions
• Zero function (z), successor (s), and projections (𝑃𝑘) (changed notation
from last time: z instead of 𝟎, P instead of U).
• We get more complex functions by two ways (rules): Composition and
Primitive recursion
• The class of functions we build that way is called Primitive Recursive Functions (PRIM)
𝑖
Composition (also called Substitution)
• We mentioned that we will be building PRIM inductively
• Assume g, h are in PRIM .
Suppose f is given by 𝑓(𝑥) = 𝑔(h(𝑥)). Then, f is also in PRIM.
Or more generally:
If𝑔 𝑦ത ,h0 𝑥ҧ ,…,h𝑙 𝑥ҧ areinPRIM,andfisgiven by
𝑓 𝑥ҧ =𝑔(h0 𝑥ҧ ,…,h𝑙 𝑥ҧ )
where 𝑦ത = (𝑦 , … , 𝑦 ), 𝑥ҧ = (𝑥 , … , 𝑥 ) 1𝑙1𝑘
Then, f is also in PRIM
Example
•𝑔𝑦,𝑦 =𝑦+3𝑦,h𝑥,𝑥,𝑥 =𝑥𝑥,h𝑥,𝑥,𝑥 =𝑥𝑥 12 1 21123 122123 13
𝑓𝑥,𝑥,𝑥 =h 𝑥,𝑥,𝑥 +3h 𝑥,𝑥,𝑥 123 112352123
= 𝑥1𝑥2 + 3𝑥1𝑥3
5
Primitive Recursion
• Recall the Fibonacci sequence
𝐹(0) = 0,𝐹(1) = 1
and 𝐹(𝑛)=𝐹(𝑛−1)+𝐹(𝑛−2)for𝑛 >1
• PRIM contains functions built that way
Primitive Recursion
• In general, if g, h are in PRIM, and f is given by 𝑓𝑥ҧ,0 =h𝑥ҧ
and
𝑓 𝑥ҧ,𝑠 𝑛 = 𝑔(𝑥ҧ,𝑛,𝑓(𝑥ҧ,𝑛))
Then, f is also in PRIM
Is the Fibonacci F in PRIM? • At first glance, it may look like it isn’t.
This is because the recursion depends on 2 former values • Yes, it is in PRIM. The proof needs some preparation
Addition is in PRIM
• Addition is a binary function: 2
+:N →N
• Sketch:
+(𝑥, 0) = 𝑥 +𝑥,𝑠𝑛 =𝑠(+𝑥,𝑛)
• Formally:
+(𝑥, 0) = 𝑃1(𝑥) 1
+ 𝑥,𝑠 𝑛 = 𝑔(𝑥,𝑛,+ 𝑥,𝑛 )
where 𝑔 𝑥,𝑛,𝑦 = 𝑃3 𝑥,𝑛,𝑠 𝑦 which is in PRIM by the composition
rule
3
Vector-valued functions
• Recall that the point from PRIM is to reinforce the intuition behind computability
• Intuitively, vector valued functions with computable components are computable
•Example: 𝑥,𝑦 →(𝑥2,3𝑦)
Can PRIM capture vector-valued functions?
• Yes, even though all functions in PRIM have N as the co-domain • Vectors are captured through pairing functions
• Those are computable bijections from N2 → N
The Cantor pairing function
• Example of a pairing function:
𝜋 𝑥, 𝑦 = 1 𝑥 + 𝑦 𝑥 + 𝑦 + 1 + 𝑥
• Note that this function is in PRIM
2
Dovetailing
• The Cantor pairing function maps (0,0) to 0, (0,1) to 1, (1,0) to 2, (0,2) to 3, (1,1) to 4, … and so on
• For proof, see Odifreddi’s p. 27 (if you want to)
Inverting the Cantor pairing function
• Moreover, we have the following cool property:
Given any natural number 𝑛, there exist a unique 𝑥 and a unique 𝑦
suchthat𝜋 𝑥,𝑦 =𝑛
• This implies that we have functions 𝜋1, 𝜋2 such that 𝑥 = 𝜋1(𝑛) and 𝑦 = 𝜋2(𝑛) (they happen to be in PRIM as well)
Notation
•𝜋(𝑥,𝑦)isusuallydenotedby 𝑥,𝑦
• We can use pairing iteratively to map from any dimension to a natural number, e.g.:
𝑥,𝑦 ,𝑧 𝑥,𝑦 ,𝑧 ,𝑤
Now we can look at the vector-valued function mentioned before 𝑥,𝑦 →(𝑥2,3𝑦)as 𝑥,𝑦 → 𝑥2,3𝑦 whichisinPRIM
Fibonacci is in PRIM
• Now we can show that the Fibonacci is in PRIM
•Weshowthat𝐺𝑛 = 𝐹𝑛,𝐹(𝑛+1) isinPRIM
• Then, it follows that 𝐹 is in PRIM because 𝐹 𝑛 = 𝜋0(𝐺(𝑛)) (composition of functions in PRIM)
• 𝐺 0 = 0,1 •𝐺𝑛=𝜋1𝐺𝑛−1 ,+(𝜋0(𝐺𝑛−1),𝜋1(𝐺(𝑛−1)))
Course-of-values recursion
• In general, PRIM contains functions obtained by recursion which depends on more than one previous values, i.e., when 𝑓(𝑥, 𝑠 𝑛 ) is in termsof𝑓 𝑥,𝑛 ,𝑓 𝑥,𝑛−1 ,𝑓 𝑥,𝑛−2 ,…
• For proof, check Odifreddi’s book Vol 1, Proposition I.7.1 (if you want to)
Break
Questions?
What else is in PRIM?
• Constant function • Multiplication
• Quotient
• Exponential
• Factorial
• Predecessor
• Max(finitetuple)
• Min(finitetuple)
• I would say: every natural number-theoretic function. Every function you can program using finite loops.
Is PRIM enough?
• Does it contain all intuitively computable functions? No
• There are computable functions which are not in PRIM
What is not in PRIM?
• The Sudan function • Ackermann function • Goodstein function
• Those are computable functions
• This means PRIM forgoes at least one intuitively computable
fundamental process
• Turns out the missing rule is minimalization
Minimalization
• Intuition:
Suppose you have a relation 𝑅 𝑥, 𝑦 on the natural numbers which is
intuitively decidable.
• Sometimes we are interested in the following:
Given a value for 𝑦, what is the smallest x such that 𝑅(𝑥, 𝑦) holds?
Adding Minimalization
• Suppose now we want to involve minimalization with what we have in PRIM
• What could correspond to 𝑅(𝑥, 𝑦) ? Ans:Iwouldsay𝑓 𝑥 =𝑦forsome𝑓inPRIM
• From which we could get the function
𝑔𝑦 =min{𝑥:𝑓𝑥 =𝑦}
• Careful: What if the minimum does not exist?
Resilience
the capacity to recover quickly from difficulties
Partial and Total functions
• We say a function 𝑓: 𝐴 → 𝐵 is total if for every 𝑥 ∈ 𝐴, 𝑓(𝑥) is defined. Otherwise, we call it partial.
• Note that PRIM functions are all total
• But we want to use minimalization
• Resilience: We consider a bigger class of functions where they can be partial
Partial Recursive Functions
• This is the class of functions obtained by the rules of PRIM and minimalization
• If 𝑔(𝑥, 𝑦) is partial recursive, then so is f given by: 𝑓𝑥 =min{𝑦:𝑔𝑥,𝑦 =0}
• To be precise, min{𝑦: 𝑔 𝑥, 𝑦 = 0} here stands for the value 𝑦0 such that 𝑔 𝑥,𝑦0 = 0 where for all 𝑦 < 𝑦0,𝑔 𝑥,𝑦0 is defined and 𝑔𝑥,𝑦0 ≠0.
Notation
•Wewrite𝑓 𝑥 ↓tomeanthatfisdefinedatx,and𝑓 𝑥 ↑otherwise.
• Minimalization (𝝁 −operator): For 𝑔(𝑥ҧ,𝑦) partial recursive,
𝑦0 = μ 𝑦 𝑔 𝑥ഥ, 𝑦 = 0 iff
𝑔𝑥ҧ,𝑦0 =0and(∀𝑦<𝑦0)𝑔𝑥ഥ,𝑦 ↓≠0.
Wrap up
Definition[Partial Recursive Functions]:
1. The initial functions
2. Obtained from partial recursive functions by Composition
3. Obtained from partial recursive functions by Primitive Recursion
4. Obtained from partial recursive functions by minimalization (μ)
• That was the inductive way to define it
• Another way is: The class of Partial Recursive Function is the smallest class which contains the initial functions and is closed under Composition, Primitive Recursion, and minimalization
• Or: It is the intersection of all classes which contain the initial functions and is closed under Composition, Primitive Recursion, and minimalization
Church’s Thesis
• Church’s thesis: A function is intuitively computable iff it is Partial Recursive
Recursive Functions
• Those are the partial recursive functions which happen to be total (with full domain N𝑘 for some 𝑘 > 0).
• We also call them computable functions
Remarks
• One can prove that: Every TM can be mimicked by a partial recursive function, and vice versa
• Church-Turing thesis (CT): A function is intuitively computable iff it can be computed in any formal sense (Turing, Recursive, URM, λ- calculus, …)
Computable and C.E. sets
• A set is computable if its indicator (characteristic) function is computable
• A set is computably enumerable (c.e.) if it is empty or it is the range of a computable function.
In other words, if not empty, then it looks like {𝑓 0 ,𝑓 1 ,𝑓 2 ,…} for some computable f (values may repeat).
Notice that this is literally enumerating (computably) the elements of the set.
Decidable and Listable (again)
• Listable = C.E.
• Decidable = Computable
We will stick to these as the original definitions
• Note that the definitions we gave are restricted to sets of natural numbers
• However, there is no loss of generality. The concepts can be extended to any sets in a world that can be coded by natural numbers
• Integers, Rationals, Letters
Alphabets, Strings, and Languages
• An alphabet Σ is a finite, non-empty set of symbols
• A string over Σ is a finite sequence (can be empty) of members of Σ • A set of strings over Σ is called a language over Σ
Coding into Natural Numbers
• Let Σ = {a, b, c, … , z} (small English letters)
• We can associate each letter with a natural number, say:
𝑎 ↔ 0, 𝑏 ↔ 1, 𝑐 ↔ 2, …
• Suppose now we want to extend the association to finite strings.
Gödel Numbering
• More precisely, we want a computable way (algorithm), by which, given any string, we find a number (unique), and if given the number, we can recover the string
• Gödel suggested the following idea:
𝑎 ↔ 2, 𝑏 ↔ 3, 𝑐 ↔ 5, … , h ↔ 19, … , 𝑙 ↔ 37, … , 𝑜 ↔ 47, …
19 11 37 37 47 h𝑒𝑙𝑙𝑜↔2 3 5 7 11
More Numbering
hello youssef
Can be coded as 2𝑔𝑛(h𝑒𝑙𝑙𝑜)3𝑔𝑛(𝑦𝑜𝑢𝑠𝑠𝑒𝑓) where gn means the Gödel number of the string
• Like this, we can associate each Program (TM) with a number! • Every partial computable function is associated with a number • Every c.e. set has a number (How do you think it is obtained?)
Remarks
• The Gödel number of the empty sequence (empty program) is set to be 1
• 𝑔𝑛 and its inverse 𝑔𝑛−1 are both in PRIM
• We let 𝑃 denote the 𝑒𝑡h Turing program, and 𝜑 the corresponding
𝑒𝑒
partial computable function (in one variable)
• More precisely, 𝑃 is the program with Gödel number e 𝑒
The Universal TM
• There exists a TM 𝑈 which if given input (𝑒, 𝑥) it runs the eth TM with input 𝑥.
• Follows from CT
Solved Problems
• Prove that: The union of two computable sets is also computable. Proof:
Let A, B be two computable sets. Let 𝐼 , 𝐼 be their indicator functions respectively. 𝐴𝐵
Since A,B are computable. Then, by definition, their indicator functions are computable.
Note that
max is in PRIM, and so is computable. (You could also say computable by CT)
It follows that 𝐼 is computable by composition. 𝐴∪𝐵
𝐼 (𝑥)=max{𝐼 𝑥 ,𝐼 (𝑥)} 𝐴∪𝐵 𝐴𝐵
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 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
Prove that: 𝐴 is computable iff 𝐴 is c.e. and 𝐴ҧ is also c.e.
Proof:
>>: If A is computable, then 𝐴ҧ is also computable (why?)
Since every computable is c.e. (we have just proved it), both A and 𝐴ҧ are c.e.
<<: We describe a program to compute 𝐼 (𝑥) for every 𝑥 ∈ N. 𝐴
From the given, we can computably enumerate both 𝐴, 𝐴ҧ.
Enumerate both in parallel.
𝑥mustshowupinoneofthem.IfitshowsupinA,then𝐼 𝑥 =1.
Otherwise, 𝐼 𝑥 = 0. 𝐴
𝐴
The Halting Set
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.not𝑒∈𝐾(contradiction)
•If not𝑒∈𝐾,then𝜑𝑒 𝑒 =𝑓 𝑒 =0i.e.𝜑𝑒 𝑒 ↓i.e.𝑒∈𝐾 (contradiction)
We showed in Proof 1 that a non-empty computable set is the range of a computable function.
Show that an infinite computable set is the range of a 1:1 computable function.