[암호학] 6. 프로그래밍 언어론

지난시간은 집합을 배우고 이젠 또 이상한걸 배우네요. 암호는 언제 배우죠?

암호랑 상관이 없어보이는 내용이 이어지는 것 같다.

하지만 이 모든 것들이 암호의 본질에 대해 필요한 내용들이니 알아보도록 하자.

 

Language

튜링머신(컴퓨터)이 해결하는 문제를 나타낸다.

용어부터 정의하고 가자.

• Symbol : 단순 문자 (0,1,a,b,c, ...)
• String : 길이가 유한한 Symbol의 배열 (01010, ababc, 00a1b, ...)
• $\lambda$ : 길이가 0인 String
• Alphabet : 길이가 유한한 Symbol 집합이고 $\Sigma$로 나타낸다. ({0,1}, {a,b,c, ..., z})
• Language : String들의 집합 ({$\lambda$, 0, 1, 01, 10, ...})
• Problem : 어떤 조건을 만족하는 Language

여기에서 중요한 것은 Problem이다.

Problem(Language)에 들어있는 원소 $x$는 그 Problem의 정답이다.

예를들어 Problem X1 = 짝수인 입력 이라는 문제를 보자

여기에 해당하는 정답은 $L1 = \{0, 10, 110, 100, 00, 000, \cdots \}$가 된다.

 

여기에서 입력 $x = 1$이 들어온다면 $x \notin L1$이므로 정답은 NO이다.

반면 입력 $x = 10$이라면 $x \in L1$이므로 정답은 YES이다.

 

이렇게 YES, NO를 도출하므로 Decision Problem이라고 부른다.

 

Problem X2 = 0으로 끝나는 정수 입력

이 정답은 역시 $L2 = \{0, 10, 110, 100, 00, 000, \cdots \}$가 될 것이다.

그렇다면 $L1 = L2$가 되므로 Problem X1 = Problem X2 라고 볼 수 있다.

 

즉, 두 문제가 같으려면 두 문제의 정답집합이 같아야 한다.

 

Alphabet

위에서 Alphabet($\Sigma$)은 길이가 유한한 Symbol 집합이라고 했다.

그럼 Alphabet 집합의 크기는 $|\Sigma|$로 표현할 수 있다.

 

정의에 따르면 $|\Sigma|$는 유한한 Symbol 집합의 크기이니 Finite Set이다.

 

String은 위의 Alphabet의 원소들을 유한개 나열하여 나타낼 수 있는 문자열의 집합이고 $\Sigma^*$로 나타낸다.

그렇다면 String의 크기는 $|\Sigma^*|$로 나타낼 것이다.

 

$|\Sigma^*|$는 Alphabet의 원소들을 "유한개"(자연수 개수) 나열할 수 있으므로 Countable Set이다.

 

예를들어 $ \Sigma = \{a,b,c\}$라고 하자.

그럼 $ \Sigma^* = \{ \lambda, a, b, c, aa, ab, ac, ba, bb, bc, ca,cb, cc, aaa, \cdots \}$가 되고 이는 무한집합이다.

이는 자연수에 대응할 수 있으므로 Countable Set이 된다.

 

Language(Problem)은 String의 부분집합이므로 $|2^{|\Sigma^*|}|$가 된다.

이는 앞서 집합론에서 배웠듯이 Countable의 Power Set이 되므로 Language는 Uncountable이다.