Computation 정의하기

computation 이란, 요구사항인 function 을 컴퓨터가 실제로 수행할 수 있도록 만든 구현체이다.
computation 을 구현하려면 다음 2가지 중에 하나를 하면 된다.

1. Circuit 을 구현한다. == 빵판에 납땜 가능한 회로도를 작성한다.
2. 알고리즘을 구현한다. == 프로그램을 코드로 작성한다.

Circuit 이라 하면 AND / OR / NOT 게이트를 가진 Boolean circuit 을 말한다.
프로그램 또한 AND / OR / NOT 연산자로 이루어진 AON-CIRC 프로그램을 말한다.

재밌는 점은 NAND 한개만 있으면, AND / OR / NOT 3가지를 전부 표현 가능하다는 점이다.
그러므로 NAND Circuit 회로도를 작성하거나,
NAND-CIR 프로그램을 코드로 작성하는게 computation 을 구현하는 가장 일반적인 방법이라 할 수 있다.

또한, Circuit 을 구현하는데 필요한 gate 의 숫자와, 프로그램을 구현하는데 필요한 코드 줄 수가 동일하다.

아래 증명은 Circuit 이나 프로그램이나, 그게 그거라는 것을 증명으로 보인 것이다.

Definition (Boolean Circuits)

$n,m,s \in \mathbb{N}$ and $m \leq s$
DAG : directed acyclic graph
A Boolean circuit with s gates, n inputs, and m outputs
is a labeled DAG $G=(V,E)$ with $s+n$ vertices.
size of a Boolean circuit = number of gates = s

Definition (Computation)

$f:\{0,1\}^n \rightarrow \{0,1\}^m$ is a function.

$C$ is a Boolean circuit with $n$ inputs and $m$ outputs.
$P$ is a AON-CIRC program of s lines with n inputs and m outputs.

$C$ computes $f$ if $C(x)=f(x)$ for $\forall x\in \{0,1\}^n$
$P$ computes $f$ if $P(x) = f(x)$ for $\forall x\in \{0,1\}^n$

Theorem 3.9 (Equivalence of circuits and programs)

$n,m,s \in \mathbb{N}$ and $m \leq s$
$f:\{0,1\}^n \rightarrow \{0,1\}^m$
$C$: Boolean circuit with $s$ gates, $n$ inputs and $m$ outputs
$P$: AON-CIRC program of $s$ lines with $n$ inputs and $m$ outputs

f is computable by $C$ $\iff$ f is computable by $P$

Proof

(i) f is computable by $C$ $\Rightarrow$ f is computable by $P$
pf
If operator of $i$-th of P has the form "foo = AND(bar,blah)"
then the $i$-th gate in the circuit will be an AND gate
that is connected to gates $j$ and $k$
where $j$ and $k$ correspond to the last lines before $i$
where the variables "bar" and "blah" were written to.

If either "bar" or "blah" is an input variable then we connect the gate to the corresponding input vertex instead.
If "foo" is an output variable, then we add the same label to the corresponding gate to mark it as an output gate.
Do the same for OR and NOT operation.
$\therefore$ $P(x) = C(x)$ for $\forall x\in \{0,1\}^n$.

(ii) f is computable by $C$ $\Leftarrow$ f is computable by $P$
pf
$v_0,\ldots,v_{s-1}$ : sorted the gates according to a topological order.
Create program $P$ of $s$ lines as follows. \medskip
If $v_i$ is an AND gate with in-neighbors $v_j,v_k$,
then we will add a line to $P$ of the form "$output_i$ = AND($input_j$, $input_k$)"
Because we work in topological ordering, we are guaranteed that the in-neighbors $v_j$ and $v_k$ correspond to variables that have already been assigned a value.

Do the same for OR and NOT gates.
$\therefore$ $C(x) = P(x)$ for $\forall x\in \{0,1\}^n$.

Theorem 3.10

AND, OR, and NOT can be computed only by composing NAND functions.

Proof

NOT(a) = NOT(AND(a,a)) = NAND(a,a)
AND(a,b) = NOT(NOT(AND(a,b))) = NOT(NAND(a,b))
OR(a,b) = NOT(AND(NOT(a),NOT(b)))

Theorem 3.17 (NAND circuits and program equivalence)

$n,m,s \in \mathbb{N}$ and $m \leq s$
$f:\{0,1\}^n \rightarrow \{0,1\}^m$
$C$: NAND circuit with $s$ gates, $n$ inputs and $m$ outputs
$P$: NAND-CIRC program of $s$ lines with $n$ inputs and $m$ outputs
f is computable by $C$ $\iff$ f is computable by $P$

Proof

From Theorem 3.9,
f is computable by Boolean circuit $\iff$ f is computable by AON-CIRC program

From Theorem 3.10,
f is computable by NAND circuit $\iff$ f is computable by Boolean circuit
f is computable by NAND program $\iff$ f is computable by AON-CIRC program

$\therefore$ f is computable by NAND circuit $\iff$ f is computable by NAND program.