공학계열 1번

[가] 금세기에 들어와 처리할 자료의 양이 많아짐에 따라 자료의 처리와 계산을 위하여 컴퓨터에 대한 의존도가 높아지고 있다. 컴퓨터는 연산과 메모리 사용에 있어서 본질적으로 이진법을 사용한다고 볼 수 있다. 이는 정수뿐만 아니라 유리수도 컴퓨터로 연산할 수 있는 대상이 됨을 의미한다. 더 나아가 무리수에 대해서도 연산의 대상으로 파악되기를 원한다. 무리수의 경우, 적당한 유리수의 극한으로서, 주어진 무리수에 대해 그 차이(오차)가 충분히 작은 유리수를 찾아 그 무리수의 근사적 대안으로 사용한다. 따라서 컴퓨터를 이용한 계산 가능한 수 또는 대상이 무엇인지 연구할 필요가 있다.

[나] 임의의 실수 $\displaystyle x$를 고정하자. 음이 아닌 정수 $\displaystyle n$에 대하여 $\displaystyle x\in I_{n+1}\subset I_n$이고, $\displaystyle n$이 커짐에 따라 $\displaystyle I_n$의 길이가 0으로 수렴하는 유리수 끝점인 폐구간들의 열 $\displaystyle \{I_0,I_1,I_2,\ldots\}$이 존재할 때, 실수 $\displaystyle x$는 계산가능하다고 말하고 $\displaystyle \{I_0,I_1,I_2,\ldots\}$을 $\displaystyle x$의 코드(code)라고 부른다. 평면 $\displaystyle \mathbb R^2$의 점 $\displaystyle (x,y)$에 대하여 $\displaystyle x,y$가 계산가능한 수이면, $\displaystyle x$의 코드 $\displaystyle \{I_0,I_1,I_2,\ldots\}$와 $\displaystyle y$의 코드 $\displaystyle \{J_0,J_1,J_2,\ldots\}$이 존재한다. 이때 사각형들의 열 $\displaystyle \{I_0\times J_0,I_1\times J_1,I_2\times J_2,\ldots\}$을 $\displaystyle (x,y)$의 코드라고 말하고, $\displaystyle (x,y)$는 계산가능하다고 한다.

[다] 계산가능성의 개념을 함수 $\displaystyle f:\mathbb R\to\mathbb R$의 경우로 확장한다. 계산가능한 실수들의 부분집합에서 실수로의 함수 $\displaystyle f$를 생각하자. 그리고 $\displaystyle f$의 정의역에 속하는 임의의 원소를 $\displaystyle x$라 하자. 적당한 $\displaystyle x$의 코드 $\displaystyle \{I_0,I_1,I_2,\ldots\}$에 대하여, $\displaystyle \{f(I_0),f(I_1),f(I_2),\ldots\}$이 $\displaystyle f(x)$의 코드가 될 때, $\displaystyle f$는 계산가능하다고 정의한다. 이때, 정의역이 동일한 계산가능한 두 함수 $\displaystyle f$와 $\displaystyle g$에 대하여 두 함수의 합과 차는 계산가능한 함수가 된다. 예컨대, 계산가능하고 동일한 정의역을 갖는 두 함수 $\displaystyle f$와 $\displaystyle g$를 생각하자. 임의의 $\displaystyle x$의 적당한 코드 $\displaystyle \{I_0,I_1,I_2,\ldots\}$에 대하여 $\displaystyle f(x)$와 $\displaystyle g(x)$의 코드 $\displaystyle \{f(I_0),f(I_1),f(I_2),\ldots\}$와 $\displaystyle \{g(I_0),g(I_1),g(I_2),\ldots\}$를 각각 찾을 수 있다. $\displaystyle f(I_n)$과 $\displaystyle g(I_n)$의 끝점들 중, 값이 작은 점들의 합과 큰 점들의 합, 이 두 점으로 만들어지는 폐구간을 $\displaystyle f(I_n)+g(I_n)$이라고 정의한다. 예를 들면 $\displaystyle [1,2]+[3,4]$는 $\displaystyle [1+3,2+4]=[4,6]$이 된다. 그러면$\displaystyle \{f(I_0)+g(I_0),f(I_1)+g(I_1),f(I_2)+g(I_2),\ldots\}$은 $\displaystyle f(x)+g(x)$의 코드가 됨을 보일 수 있다. 따라서 $\displaystyle f+g$는 계산가능하다.

[라] 평면에서 정의된 함수 $\displaystyle F:\mathbb R^2\to\mathbb R$를 생각한다. 계산가능한 $\displaystyle \mathbb R^2$의 부분집합에서 실수로의 함수 $\displaystyle F$를 생각하자. 그리고 $\displaystyle F$의 정의역에 속하는 임의의 원소를 $\displaystyle (x,y)$라 하자. 만약 $\displaystyle (x,y)$의 적당한 코드 $\displaystyle \{I_0\times J_0,I_1\times J_1,I_2\times J_2,\ldots\}$에 대하여, $\displaystyle \{F(I_0\times J_0),F(I_1\times J_1),F(I_2\times J_2),\ldots\}$이 $\displaystyle F(x,y)$의 코드가 될 때, $\displaystyle F$는 계산가능하다고 정의한다. 여기서 $\displaystyle I_n\times J_n$은 카르테시안 곱으로서 $\displaystyle \{(a,b)\mid a\in I_n,b\in J_n\}$을 나타낸다.