2.2 Coding and Counting Programs Flashcards
1
Q
How do we encode finite data structures into the natural numbers
A
Define a bijective function between something and N
2
Q
While programs compute functions from …. to ….
A
Z^n→Z^m
3
Q
How do we map Z to N?
A
2x if x ≥ 0
-2x - 1 else
4
Q
How do we code pairs as single numbers?
A
∅(n,m) =2^n (2m+1) - 1
5
Q
How do we code lists?
A
f[] = 0
f( s : l ) = 2^n(2f(l) + 1)
6
Q
How do we show we can count (enumerate) while programs?
A
A bijection between while statements and N
7
Q
What is a Godel number?
A
given a while program S, γ(S) is its Godel number
γ: Stm → N
8
Q
The set of while programs is…
A
Countably infinite
9
Q
How do we create a universal while program?
A
Write a program to compute the translations
