지난 시간에 Computation 을 엄밀히 정의하면서,
computation 을 Circuit 으로 구현하든, 프로그램으로 구현하든,
그게 그거라는 것을 보였다.
또한 NAND 하나로, AND / OR / NOT 3가지를 다 표현 가능하니,
NAND 하나만으로 computation 을 구현할 수 있다.
이번 시간에는 NAND 하나만으로, 정말로 모든 함수를 compute 할 수 있는지 증명해보려 한다.
Definition (Lookup function)
LOOKUPk:{0,1}2k+k→{0,1}
Lookup function of order k is defined as follows:
x=x0x1…x2k−1∈{0,1}2k
i=i0i1…ik−1∈{0,1}k
LOOKUPk(x,i)=xi∈{0,1}
where xi = ith entry of x.
즉 Lookup function 이란, i bit string 을 숫자로 바꾸어서,
해당하는 숫자의 위치에 있는 i 번째 bit 를 x bit string 에서 가져오는 함수이다.
Lemma 4.11 (Lookup recursion)
k≥2
a=LOOKUPk−1(x0,…,x2k−1−1,i1,…,ik−1)
b=LOOKUPk−1(x2k−1,…,x2k−1,i1,…,ik−1)
LOOKUPk(x0,…,x2k−1,i0,…,ik−1)={abif i0=0if i0=1
Proof
If i0=0, then the index i is in {0,…,2k−1−1}.
Perform the lookup on the first half of x.
Then, LOOKUPk(x,i)=LOOKUPk−1(x0,…,x2k−1−1,i1,…,ik−1)=a
If i0=1, then the index i is in {2k−1,…,2k−1}.
Perform the lookup on the "second half" of x.
Then, LOOKUPk(x,i)=LOOKUPk−1(x2k−1,…,x2k−1,i1,…,ik−1)=b
증명이라기보다는 Lookup recursion 함수에 대한 설명 같다.
Theorem 4.10 (Lookup function 의 구현)
LOOKUPk:{0,1}2k+k→{0,1} is a lookup function.
For ∀k>0, ∃ NAND-CIRC program that computes LOOKUPk.
Moreover, the number of lines in this program ≤4⋅2k
Proof
For k=1,
LOOKUP1:{0,1}3→{0,1} can be computed by
4 line NAND-CIRC program.
def IF(cond,a,b):
notcond = NAND(cond,cond)
temp = NAND(b,notcond)
temp1 = NAND(a,cond)
return NAND(temp,temp1)
For k≥2,
We can apply Lemma 4.11.
a=LOOKUPk−1(x0,…,x2k−1−1,i1,…,ik−1) \
b=LOOKUPk−1(x2k−1,…,x2k−1,i1,…,ik−1)
LOOKUPk(x0,…,x2k−1,i0,…,ik−1)={abif i0=0if i0=1
Recursively call LOOKUPk until k becomes 1.
Then, we have 4⋅2k lines of NAND-CIRC program.
Theorem 4.12 (Universality of NAND)
For n,m>0 and function f:{0,1}n→{0,1}m
∃ constant c>0 such that
∃ Boolean circuit with at most c⋅m2n gates that computes the function f.
Proof
For ∀ function f:{0,1}n→{0,1},
we can write a NAND-CIRC program that does the following:
- Initialize 2n variables of the form
temp = NAND(X[0], X[1])
one = NAND(X[0], temp)
zero = NAND(one, one)
x0=f(00⋯0), ⋯, x2n−1=f(11⋯1)
This requires 3+2n lines of code.
- Compute LOOKUPn on the 2n variables initialized in the previous step,
with the index variable i=i0i1…in−1 being the input variables.
LOOKUPn(x0,…,x2n−1,i0,⋯,in−1)
This requires at most 4⋅2n lines of code by Theorem 4.10.
y=y0…ym−1∈{0,1}m
l∈[m]={0,1,…,m−1}
total number of lines for computing one bit yl∈{0,1}
≤(3+2n)+(4⋅2n)=3+5⋅2n
Repeat the computation of one bit yl∈{0,1} for m times.
Then, we can get y=y0…ym−1∈{0,1}m
∴ the total number of lines for computing function ≤m⋅(3+5⋅2n)
This completes the proof.