계산 가능성 이론
위키백과 ― 우리 모두의 백과사전.
- 계산가능성 이론을 수리논리학의 범주에서 보려면, 재귀이론으로 가십시오.
전산학에서, 계산가능성 이론(計算可能性 理論, computability theory)은 계산이론의 한 갈래로서 계산모델을 이용하여 어떤 문제가 계산이 가능한지를 연구하는 이론이다.
계산가능성 이론은 어떤 문제가 풀릴 수 있는가를 따지기 때문에, 어떻게 문제가 효율적으로 풀릴 수 있겠는가를 다루는 계산 복잡도 이론과는 구별된다.
목차 |
[편집] 소개
컴퓨터 과학의 핵심과제는 컴퓨터로 푸는 문제들을 이해하여 연산장치의 한계를 밝히는 것이다. 현대의 연산장치는 거의 무한대의 계산능력을 지닌것 처럼 보인다. 그래서 충분한 시간이 있으면 우리는 어떤 문제든 컴퓨터로 풀 수 있을거라고 생각하기 쉽다. 그러나 쉽게 풀 수 있을것 같은 문제를 풀기에 엄청난 자원이 주어졌다고 해도, 컴퓨터의 계산능력에는 한계가 있으며, 증명 가능하다.
이 분야에서, 컴퓨터 과학자들은 다음 물음에 답하기 위해서 대개 컴퓨터의 능력에 대해 언급한다.
- 형식 언어가 주어지고, 문자열 하나가 있다, 이 문자가 그 언어에 사용되느냐?
이 질문에 대답하는 것은 무척이나 어려우며, 답을 하기 위한 예도 난해하다. 우선 주어진 언어를 소수(2,3,5,7,11...)개의 문자를 가진 문자열들의 집합이라고 정의하자. 그러면 어떤 문자열이 주어진 언어에 쓰이는가를 밝히는것은 주어진 문자열의 문자의 개수가 소수이냐를 밝히는 것과 동일하다. 다른 예로서 거꾸로 읽어도 같은 구절들이나 a로된 모든 문자열들의 집합을 언어로 정의할 수 있고 마찬가지로 질문에 답할 수 있다. 컴퓨터가 이러한 문제를 다루는 경우는 매우 흔하다.
그런데, 어떤 실제의 관점에서 이러한 것들이 유효할 것인가? 어떻게 특정한 문제가 컴퓨터상에서 풀릴수 있는지를 이해할 것인가? 바로 이러한 물음에 답하는 것이 계산가능성 이론의 목적이다.
[편집] 계산에 대한 표준모형
계산가능성 이론의 핵심과제를 풀기 위해서 컴퓨터가 무엇인가를 정식으로 정의해야한다. 계산에 쓰이는 많은 모형중에서도, 가장 널리 알려진 모형은 튜링 기계이며, 현존하는 가장 강력한 모형이다. 여기에 다음과 같은 다른 형태의 모형도 존재한다.
- 결정론적 유한상태기계
- 비교적 간단한 이 계산모형은 deterministic finite automaton (DFA), 간단히 유한 상태 기계(finite state machine)로 불린다. 현존하는 모든 연산장치들은 유한 상태 기계모형으로 설명 가능하다. 유한 상태 기계는 상태, 입출력, 입력에 따른 상태 천이식으로 구성된다. 입력 장치에서 한번에 문자 한개를 전달하면, 현재 상태에 있어서의 상태 천이는 입력에 따라 이루어진다. 만약 입력에 맞는 상태 천이가 존재한다면, 기계는 새로운 상태로 변하게 된다. 일부 상태는 accepting 상태로 정의되는데, 일련의 입력 끝에서 기계가 accepting 상태에 있다면 해당 입력 전체가 수락된다.
- 내리누름 오토마타
- 정해지지 않은 크기를 가진 실행 스택을 가졌다는 것을 제외하고는 위의 유한 상태 기계와 유사하다. 상태 천이는 기존의 기능 외에, 부가적으로 스택에 symbol을 추가할 것인가 제거할 것인가를 결정할 수 있다.
- 튜링 기계
- 입력 방식이 실행 "tape"이라는 점을 빼고는 유한 상태 기계와 유사하다. 실행 "tape"는 "head"를 이동시키는 방식으로 읽고 쓰기를 수행하며, 크기가 정해지지 않은 무한한 공간을 가진다. 튜링 기계는 따로 실제 기계의 유한성을 고려하지 않지만, 컴퓨터과학에서 가장 중요한 계산 모형이다.
[편집] 계산모형의 계산능력
언급된 계산 모형들을 사용하여, 각 기계의 한계를 정의할 수 있다. 한계란 "해당 장치가 다룰 수 있는 형식 언어는 어떠한 종류인가?" 에 대한 답이다.
[편집] 유한상태기계의 계산능력
컴퓨터과학자들은 유한 상태 기계 모형을 만족하는 기계가 받아들일 수 있는 언어를 regular language라 한다. 유한 상태 기계에서 가능한 상태는 유한개이기 때문에, regular하지 않은 언어를 발견하게 될 수도 있지만, 우리는 무한개의 state가 가능한 언어를 설계할 필요가 있다.
예로, a와 b가 같은 개수만큼 섞여서 있는 문자열들의 집합을 가진 언어를 생각해 보자. 이 언어가 finite state machine모형으로 다룰수 없는 이유를 알기 위해서, 우선 모형을 만족하는 M이라는 기계가 있다고 하자. M은 유한한 n개의 state를 가져야한다. 그다음 앞쪽에 a가 (n + 1)개, 그 뒤에 b가 (n + 1)개 있는 문자열 x를 생각해 보자.
기계 M 이 문자열x 를 읽는다, 문자열 'a'를 읽을때 같은 state 가 적어도 한쌍 나오게 된다. 왜냐하면 'a'가 (n + 1) 개 있고 state가 n 개 있으므로 pigeonhole principle를 적용할 수 있기 때문이다. 이 state 를 S 라 하겠다. 그리고 state S 가 정해둔 횟수만큼 나타날때까지 읽은 'a'의 개수를 d 라 하면 우리는 S 가 두번째로 나타날때 d 가 양수이고 기계가 다시 S state가 될것이라는 걸 알게된다. 기계가 (n + d + 1) 번째의 'a'문자를 읽든 (n + 1) 번째의 'a'를 읽든 같은 state 가 된다는 것이다. 이는 곧 기계가 문자열 x 를 받아들인다면, (n + d + 1) 번째의 'a'와 (n + 1) 번째의 'b'를 받아들인다는 것이다. 이런 것은 'a'와 'b'가 같은 개수가 있는 문자열이 있는 언어가 아니다.
따라서 이 언어는 어떤 finite state machine도 제대로 받아들일 수 없으며 또한 regular language가 아니다. 더 일반적인 형태로 보이기 위해서 Pumping lemma for regular languages를 쓰는데, 훨씬 더 많은 종류의 언어가 finite state machine로 이식될 수 없다는 것을 보일 수 있다.
많은 이들은 자신이 이러한 언어를 이식하는 프로그램을 desktop PC로 쉽게 작성했다는 이유로 이 결과에 반대할 것이지만, 이미 desktop PC 나 현존하는 모든 컴퓨터들이 finite state machine 이라는 걸 말해두었다. 물론 그러한 프로그램을 작성하기가 쉬운 것은 사실이지만 엄연히 제한은 존재한다는 것을 알아야 한다 : 컴퓨터의 메모리 용량. 컴퓨터의 메모리 용량이 입력된 문자들의 개수를 세다가 바닥날때까지 문자열을 입력할 수 있고 결국 바닥나서 overflow 할 것이다. 그러면 컴퓨터는 전에 있던 state가 되는 것이다. 이처럼 많은 문자열을 이식할 수 있다고 해도 이식할 수 없는 언어의 문자열이 있다는 것이고, 이러한 사실은 regular language가 어떻게 desktop PC 등에 적응하는지 이해하도록 할것이다.
[편집] 내리누름 오토마타의 계산능력
컴퓨터 과학자들은 push-down automaton으로 받아들일 수 있는 언어를 Context-free language라 정의한다. 특정될 수 있는 것은 Context-free grammar라 한다. 'a'와 'b'가 같은 개수만큼 있는 언어는 regular language 가 아니라고 전에 밝혔다. 그러나 push-down automaton 으로는 성립될 수 있다. 물론 일반적으로 push-down automaton 이 finite-state machine 와 비슷하게 동작할 수 있어서, regular 한 언어를 성립시킬 수 있다. 그러므로 이 계산 모형은 finite state machine보다 더 넓은 한계를 가진다고 엄밀하게 말할 수 있다.
그러나 push-down automaton으로도 성립될 수 없는 언어가 있다. regular expression에서 이와 같은 결과가 나타나는데 여기서 상세히 말하지는 않겠다. Pumping lemma for context-free languages도 여기에 해당된다. 이러한 언어의 예로 소수의 집합도 있다
[편집] 튜링 기계의 계산능력
Turing machine 은 모든 context-free language 를 성립시킬수 있으며, push-down automata로 성립하지 않는 언어도 성립시킨다, 예로 소수로 이루어진 언어를 성립시킨다. 그러므로 이 모형은 엄밀하게 따지면 더욱 넓은 한계를 가진 계산 모형이다.
Turing machine 이 자신의 input tape를 "back up" 할 수 있기 때문에, 긴 시간이 주어진다면 Turing machine이 이전에 말한 계산 모형으로는 할 수 없던 계산을 수행할 수 있다. 또 Turing machine 은 어떤 입력이든지 처리할 수 있도록 설계될 수 있다. 그래서 우리는 Turing machine의 입출력이 마비되더라도 한 언어를 성립시킨다고 말한다. 이런 식으로 성립시킬 수 있는 언어를 recursive language라 한다. 우리는 더 나아가서 Turing machine이 한 언어를 성립시킬때 마비되더라도 그 외의 언어를 성립시킬때는 잘 동작할 것이라고 말할 수 있다. 이러한 Turing machine은 입력한 문자열이 그 언어에 속하는지를 말해 주는데, 입력한 문자가 그 언어에 속하지 않는다는 결과가 나왔다고 이를 확신해선 안된다. 이번에만 그렇게 나올 수 있기 때문이다. 이러한 Turing machine 으로 성립되는 언어를 recursively enumerable language라 한다.
튜링 머신은 대단히 넓은 한계를 가진 계산모형이고 또 그렇다고 알려져 있다. Turing machine 의 정의를 개선하여 그 한계를 극복하려 했지만, 실패했다. 예를 들어보자. Turing machine 에 추가로 tape를 더하여 2-3차원 무한 영역을 구현하는것은 단위 1차원 tape을 가지는 Turing machine로도 구현할 수 있다. 이러한 모형들은 한계를 극복할 여지가 없는 것이다. 사실, Church-Turing thesis로 Turing machine에서 성립될 수 없는 언어를 확정할 수 있게 하는 합리적인 계산 모형이 없다는 추측을 할 수 있다. 여러 사람들이 Turing machine의 한계를 극복한 계산 모형을 제안하였지만, 그러한 것들은 비현실적이고 비합리적인것 같다. (아래에 보세요).
그러므로 Turing machine 은 계산이 가능한 범위는 무엇인가와 그것과 관련된 물음을 이해할 수 있게 하는 가장 의미있는 수단을 제공한다는 것이다. 그렇다면 나오는 질문은: recursively enumerable하나 recursive이지 않은 언어가 존재하느냐? 그리고 recursively enumerable하지도 않은 언어도 있겠느냐?
[편집] 정지문제
- 이 부분의 본문은 정지문제입니다.
컴퓨터 과학에서 가장 중요한 문제들중 하나인 halting problem 은 평소에 컴퓨터가 어떻게 다루어지는가와, 계산가능성이론에 대한 핵심적인 부분을 다루고 있다. 그 문제는 다음과 같다:
- Turing machine과 initial input에 대한 충분한 설명이 있을때 program이 그 입력을 먹고 멈출때가 있겠느냐. 그렇지 않다면 멈추지 않고 잘 작동하겠느냐.
여기선 소수의 개수나 거꾸로 읽어도 같은 문구같은 단순한 문제를 다루려는게 아니며, 본론으로 들어가서 한 Turing machine 이 다른 Turing machine 에 대한 물음에 답하게 하려는 것이다. 이러한 물음에 대답할 수 있는 Turing machine을 설계하는것이 불가능할 수 있다는걸 보일 수 있다.(Halting problem 을 보세요)
결국, 모든 경우에서 주어진 program이 어떤 input에 마비되는지를 확실히 알려면 단순히 작동시켜보고 기계가 마비되는걸 보는 수 밖에 없다. 기계가 마비되면 당신은 그걸 알게 되는 것이니까. 그러나 기계가 마비되지 않는다면 이것이 마비가 될지 알 길이 없을 것이다. Turing machine을 마비시킬 수 있는 모든 가능한 input stream를 가지고 있는 모든 Turing machine description로 구성된 언어는 recursive이지 않다. 따라서 halting problem 은 noncomputable 혹은 undecidable 하다.
halting problem을 더욱 확장한 것으로 Rice's Theorem가 있는데, Turing machine이 수락하는 모든 nontrivial 한 속성의 언어는 undecidable하다고 말한다.
[편집] recursive languages 가 아닌 language가 Turing machine에 이식된다면?
The halting problem 은 쉽게 풀리는 편이다. 그러나, Turing machine이 어떠한 입력을 먹더라도 잘 작동하도록, 우리가 허락한다면, The halting language는 recursively enumerable하게 된다. 그리고 그밖에도, recursively enumerable하지 않은 언어를 구상하는게 가능하다.
the halting language가 아닌 언어가 한 예이다. 이 언어에는 어떠한 Turing machine에 먹이면 잘 동작하는 문자열과 그 문자열을 먹어서 잘 동작한 Turing machine을 묶어 놓았다. 이제 이 언어가 recursively enumerable하지 않는다를 보이려 한다. 우리는 Turing machine M 을 구상할 것인데, 그 언어가 잘 동작하는 Turing machine에 대해 확실한 답을 내주는게 가능하다. 그러나 이 언어는 결국 정지하는 일이 생기는 어떠한 Turing machine에 대하여도 잘 작동하는게 허락되었다. 그럼, 우리는 또다른 Turing machine M'을 구상하여 이 turing machine이 M의 작동과정을 구현해내도록 하자. 즉, 주어진 입력에 대하여 반응하는 the machine의 작동을 그대로 따라가면서, the two program의 작동이 time-sharing의 성질을 따르도록 하자. direct simulating이 simulating 하는 프로그램이 정지하면 direct simulation은 결국 멈출것이라는 걸 알고, M 의 simulation은 input program이 정지하지 않으면 결국 중지될 것이라는 추측에 의해서, 우리는 M'은 결국 프로그램이 멈추는 일을 simulating할 일이 생긴다는걸 안다. 그러므로 M'은 the halting problem의 답을 결정한다. 그런데 우리는 the halting problem이 undecidable이라는 걸 이전에 보였다. 여기서 우리는 모순점을 발견한다. 따라서 우리는 M 이 존재하지 않는다는걸 보이게 되며, 따라서 the halting language가 아닌 언어는 recursively enumerable하지 않다.
[편집] 가상의 계산모형
The Church-Turing thesis conjectures that there is no reasonable model of computing more powerful than a Turing machine. In this section we will explore some of the "unreasonable" ideas for computational models which violate this conjecture. Computer scientists have imagined many varieties of hypercomputers. Recursion theory is the branch of mathematical logic that deals rigorously with these models of computation.
[편집] 무한실행
Imagine a machine where each step of the computation requires half the time of the previous step. If we normalize to 1 time unit the amount of time required for the first step, the execution would require
time to run. This infinite series converges to 2 time units, which means that this Turing machine can run an infinite execution in 2 time units. This machine is capable of deciding the halting problem by directly simulating the execution of the machine in question.
[편집] 신탁기계
- 이 부분의 본문은 신탁기계입니다.
So-called Oracle machines have access to various "oracles" which provide the solution to specific undecidable problems. For example, the Turing machine may have a "halting oracle" which provided immediately whether a given Turing machine will ever halt on a given input.
[편집] 초월계산의 한계
Even these machines, which seemingly represent the limit of computation that we could imagine, run into their own limitations. While each of them can solve the halting problem for a Turing machine, they cannot solve their own version of the halting problem. That is, an Oracle machine cannot answer the question of whether a given oracle machine will ever halt.
[편집] 계산가능성 이론의 역사
계산가능성 이론은 일차논리에 그 뿌리를 두고 있으며, 정지문제 및 재귀와 관련된 많은 문제들은 불완전성 정리와 밀접하게 연관되어 있다. 다비드 힐베르트와 쿠르트 괴델은 일차논리의 기초를 쌓았다. 계산가능성 이론에 앞서 알론조 처치와 스티븐 콜 클리네는 람다 셈법을 연구했다. 앨런 튜링은 현대 전산학의 아버지라 불릴 수 있을 만큼 계산가능성 이론과 복잡도 이론의 중대한 기틀을 다졌다. 튜링의 가장 유명한 업적은 튜링 기계를 제안하여 판정문제를 해결한 것이다.
[편집] 같이 보기
[편집] 참고문헌
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing ISBN 0-534-94728-X Part Two: Computability Theory, chapters 3–6, pp.123–222.
- Christos Papadimitriou, Computational Complexity, Addison Wesley ISBN 0201530821, Chapter 3: Computability, pp.57–70.
분류: 정리가 필요한 문서 | 계산 이론
