위상수학을 공부하다가, 계산 이론을 보고 있으니 심신이 정화되는 듯한 기분이 든다.

공부 중인 레퍼런스 책

Computation

intput -> output

• 임의의 input 과 output 을 모두 bit 로 표현할 수 있을지 증명해보자

증명의 조건

• Find function:(object -> bit) which is injective

Function 복습

f: X -> Y

1. for every x, there exists y such that f(x) = y
2. x = y implies f(x) = f(y)

• X: domain
• Y: codomain
• image: {f(x) | x is element of X}

Injective(1 to 1 function)

x != y implies f(x) != f(y)

Surjective(onto function)

For every y, there exist x such that y = f(x)

Bijective

Bijective == (Injective & Surjective)

Natural Number to Bit

NtS: Number to String
0 과 1로 모든 Natural Number 를 표현하고 싶다.

parity(n) = n is odd ? 1 : 0 = n % 2
NtS(n) = NtS([n/2])parity(n)

Integer to Bit

ZtS(n) = n >= 0 ? 0NtS(n) : 1NtS(n)

or Two's complement

Rational Number to Bit

a / b => ZtS(a)ZtS(b)

Real Number to Bit (Cantor's Theorem)

불가능하다. Real Number 은 Uncountable 하기 때문이다.

Cantor's Theorem 증명하는 법 외워두기