2.3 Computable Functions Flashcards
A function f: N → N is countable if?
There is a while program S such that:
⟨S,σ⟩⇒σ’
then
σ’(x) = f(n)
A function is computable if we can write a while program to compute it. We can construct computable functions from computable functions.
Is a partial function computable?
Yes using if statements
What is the Pigeon hole principle?
What does this mean for infinite sets?
If n items can be put into m containers with n > m then at least one container contains more than one item.
There is no injective function whose co-domain is smaller than its domain
How do you show there are uncountably many functions N → N ?
Assume countably many
If countable many, we can enumerate them.
So there is a bijection f(N → N) → N
Each function must be different from the others.
Construct a new function which is different from all the others and hence show our enumeration was incomplete.
Construct new function by adding one to the diagonal terms in the table above.
A predicate is decidable if?
There is a computable function N → N:
f(x) = 1 if P(x) holds
0 if P(x) doesn’t hold
The total function f: N → N of predicate P is?
And the associated program in while is?
The characteristic function of P
A decision procedure for P
A partial function P is partially decidable if?
There exists a computable partial function f: N → N:
f(x) = 1 if P(x) holds
0 if P(x) doesn’t hold
The partial function f is the …. of P and the associated program in while the ……. for P
Partial characteristic function
Partial decision procedure
A model of computation if universal if?
It can model itself. We can write a program in the language that can simulate all other programs that can be written in the language.
How do we define a universal program?
Encode programs as numbers. Take that as input and use γ^(-1) to lookup the relevant program and run it
Suppose that program S is the value of y^(-1)(i), define the function associated with the ith program
n_i(k) = σ’ (x) if ⟨S,σ[x↦k]⟩ ⇒σ’
undefined otherwise
The universal program computes?
The universal function
What is the church Turing thesis?
All reasonable models of computing are the same: if a function is computable then we can write a program in any language to compute it.
We can simulate all while programs using a single while program
We can simulate all java programs using a single java program
We can simulate all while programs using a java program
