계산 가능성 이론

위키백과 ― 우리 모두의 백과사전.

계산 가능성 이론을 수리논리학의 범주에서 보려면, 재귀 이론을 참고하십시오.

전산학에서, 계산 가능성 이론(計算可能性理論, computability theory)은 계산 이론의 한 갈래로서 계산 모형을 이용하여 어떠한 문제를 계산할 수 있는지를 연구하는 이론이다.

계산 가능성 이론은 어떤 문제가 풀릴 수 있는가를 따지기 때문에, 어떻게 문제가 효율적으로 풀릴 수 있겠는가를 다루는 계산 복잡도 이론과는 구별한다.

[편집] 소개

컴퓨터 과학의 핵심과제는 컴퓨터로 푸는 문제들을 이해하여 연산장치의 한계를 밝히는 것이다. 현대의 연산장치는 거의 무한대의 계산능력을 지닌것 처럼 보인다. 그래서 충분한 시간이 있으면 우리는 어떤 문제든 컴퓨터로 풀 수 있을거라고 생각하기 쉽다. 그러나 문제가 쉬워 보이고 또 엄청난 자원이 주어졌다고 해도 컴퓨터의 계산능력에는 한계가 있으며 한계성을 증명할 수 있다.

컴퓨터 과학자들은 이 분야를 연구하기 위해 주로 컴퓨터가 다음 문제를 대답할 수 있는지에 역점을 둔다.

형식 언어가 주어지고, 문자열 하나가 있다, 이 문자열이 그 언어의 원소인가?

주어진 언어를 소수(2,3,5,7,11...) 길이의 문자열 집합이라고 정의하자. 그러면 어떤 문자열이 주어진 언어의 원소인지는 주어진 문자열의 길이가 소수인지와 같은 문제가 된다. 다른 예로 회문의 집합이나 'a'로만 이루어진 모든 문자열의 집합 등을 생각할 수 있다. 컴퓨터가 이러한 문제를 다루는 경우는 매우 흔하다.

그렇다면 어떤 관점에서 문제가 어려운지를 판단해야 하는가? 특정한 문제가 컴퓨터로 풀기에 얼마나 난해한지를 어떻게 정의할 것인가? 이러한 물음에 답하는 것이 계산가능성 이론의 목적이다.

[편집] 계산 모형

계산 가능성 이론의 핵심과제를 풀기 위해서는 먼저 컴퓨터를 정의해야 한다. 계산에 쓰이는 많은 모형중에서도 가장 널리 알려진 모형은 튜링 기계이며 현존하는 가장 강력한 모형이다. 여기에 다음과 같은 다른 형태의 모형도 존재한다.

결정적 유한 상태 기계: 비교적 간단한 이 계산모형은 결정적 유한 오토마타(deterministic finite automaton, DFA), 간단히 유한 상태 기계로 불린다. 현존하는 모든 연산 장치들은 유한 상태 기계모형으로 설명 가능하다. 유한 상태 기계는 상태, 입출력, 입력에 따른 상태 천이식으로 구성된다. 입력 장치에서 한번에 문자 한개를 전달하면, 현재 상태에 있어서의 상태 천이는 입력에 따라 이루어진다. 만약 입력에 맞는 상태 천이가 존재한다면, 기계는 새로운 상태로 변하게 된다. 일부 상태는 수락(accepting) 상태로 정의되는데, 일련의 입력 끝에서 기계가 수락 상태에 있다면 해당 입력 전체를 수락한다.

내리누름 오토마타: 정해지지 않은 크기를 가진 실행 스택을 가졌다는 것을 제외하고는 위의 유한 상태 기계와 거의 같다. 상태 천이는 기존의 기능 외에, 부가적으로 스택에 기호(symbol)를 추가하거나 뺄 수 있으며 스택 위의 기호에 따라 다른 상태로 이동할 수도 있다.

튜링 기계: 입력 방식이 실행 테이프(tape)라는 점을 빼고는 내리누름 오토마타와 유사하다. 실행 테이프는 헤드(head)를 이동시키는 방식으로 읽고 쓰기를 수행하며 무한히 길다. 튜링 기계는 실제 기계와는 달리 유한성을 고려하지 않지만 컴퓨터 과학에서 가장 중요한 계산 모형이다.

[편집] 계산모형의 계산능력

앞서 말한 계산 모형들이 어떤 종류의 형식 언어를 표현할 수 있는지에 따라 각 모형의 한계를 알 수 있다.

[편집] 유한상태기계의 계산능력

컴퓨터 과학자들은 유한 상태 기계 모형을 만족하는 기계가 받아들일 수 있는 언어를 정규 언어라 한다. 유한 상태 기계에서 가능한 상태는 유한개이다. 따라서 어떤 언어가 정규 언어가 아니라는 것을 보이기 위해서는 그 언어를 표현하기 위해 무한개의 상태가 필요하다는 것을 보여야 한다.

예를 들어 a 와 b 를 같은 개수만큼 포함하는 문자열들의 집합을 생각해 보자. 이 언어가 유한 상태 기계 모형으로 다룰 수 없다는 것을 보이기 위해 그런 기계 $M$ 이 있다고 하자. $M$ 은 유한하므로 상태의 수를 $n$ 개라 할 수 있다. 한편 앞에 a가 $(n + 1)$ 개, 뒤에 b가 $(n + 1)$ 개 있는 문자열 $x$ 를 생각하자.

기계 $M$ 이 문자열 $x$ 를 읽어 들이면 문자열 'a'를 읽을때 적어도 한 상태를 두 번 거치게 된다. 'a'가 $(n + 1)$ 개 있고 상태가 $n$ 개 있으므로 비둘기집 원리를 적용할 수 있기 때문이다. 이 상태를 $S$ 라 하자. 그리고 상태 $S$ 가 처음 나온 때로부터 두번째 등장할 때까지 읽은 'a'의 개수를 $d$ 라 하자. 즉, $S$ 에서 d 만큼의 'a'를 받아들였을때 다시 $S$ 상태가 된다는 것이고 따라서 기계가 $(n + d + 1)$ 개의 'a'문자를 읽든 $(n + 1)$ 개의 'a'를 읽든 최종에는 같은 상태가 된다. 이는 곧 기계가 문자열 $x$ 를 받아들인다면, $(n + d + 1)$ 개의 'a'와 $(n + 1)$ 개의 'b'로 구성된 문자열도 받아들인다는 것이다. 이것은 $M$ 이 'a'와 'b'가 같은 개수가 있는 문자열만 받아들인다는데 모순이 된다.

따라서 이 언어는 어떤 유한 상태 기계로도 표현할 수 없으며 따라서 정규 언어가 아니다. 더 일반적인 형태로 보이기 위해서 정규 언어에 대한 펌핑 렘마를 쓰는데, 많은 언어들이 유한 상태 기계로 나타낼 수 없다는 것을 보이는데 쓰인다.

아마 많은 사람들이 이 결과를 의아하게 생각할 것이다. 이러한 언어를 인식하는 프로그램을 컴퓨터로 작성하는 것이 매우 쉽기 때문이다. 하지만 위에서 데스크톱 PC 등 현존하는 모든 컴퓨터들이 유한 상태 기계라고 말하였다. 이것은 컴퓨터에도 엄연히 컴퓨터의 메모리 용량 같은 제한이 존재하기 때문이다. 문자열의 길이가 길어지면 문자의 개수를 세는데 컴퓨터의 메모리 용량을 다 쓸 것이고, 결국 바닥나 오버플로우할 것이다. 아무리 많은 문자열을 인식할 수 있다고 해도 결국 인식할 수 없는 문자열이 있다. 이러한 사실들은 정규 언어가 어떻게 데스크톱 PC 등에 적용되는지를 이해할 수 있게 해 준다.

[편집] 내리누름 오토마타의 계산능력

컴퓨터 과학자들은 내리누름 오토마타로 받아들일 수 있는 언어를 문맥 자유 언어라 정의한다. 이 언어는 문맥 자유 문법으로도 표현할 수 있다. 앞에서 'a'와 'b'가 같은 개수만큼 있는 언어는 정규 언어가 아니라고 하였는데, 내리누름 오토마타로는 표현할 수 있다. 일반적으로 내리누름 오토마타가 유한 상태 기계처럼 동작할 수 있고 따라서 정규 언어를 받아들인다. 그러므로 이 계산 모형은 유한 상태 기계보다 더 강력하다.

하지만 내리누름 오토마타로도 표현할 수 없는 언어가 있다. 정규 언어에서와 비슷하게 찾을 수 있는데, 예로는 소수의 집합이 있다(상세히 설명하지는 않겠다.) 정규 언어와 비슷하게, 문맥 자유 언어에 대한 펌핑 렘마도 있다.

[편집] 튜링 기계의 계산능력

튜링 기계는 모든 문맥 자유 언어를 표현할 수 있으며 내리누름 오토마타로 표현할 수 없는 언어도 표현할 수 있다. 예를 들어 소수로 이루어진 언어를 표현할 수 있다. 따라서 이 모형은 앞의 두 모형보다 더욱 강력하다.

튜링 기계는 자신의 입력 테이프에 내용을 저장하는 기능이 있기 때문에 긴 시간이 주어진다면 다른 계산 모형으로는 할 수 없었던 일들을 할 수 있다. 튜링 기계는 어떤 입력에 대해 영원히 멈추지 않을 수 있다. 만약 튜링 기계가 모든 입력에 대해서 멈추고 결과를 출력한다면 언어를 결정한다라고 하고 그 언어를 순환 언어라 한다. 만약 튜링 기계가 언어의 원소에 대해서는 항상 멈추고 결과를 출력하지만 언어 밖의 문자열에 대해서는 멈추지 않을 수도 있다면 그 언어를 순환 열거 언어라 한다.

튜링 기계로는 많은 일을 할 수 있다. 많은 이들이 튜링 기계 이상의 기계를 만들어내려 노력했지만 모두 실패하였다. 예를 들어 튜링 기계의 테이프 수를 늘려 2-3차원 무한 영역으로 확장한다 하더라고 이것은 1차원 테이프로도 구현할 수 있다. 이런 모형들은 튜링 기계보다 더 편리할 수는 있지만 더 강력하지는 않다. 사실상 튜링 기계 이상의 합리적인 계산 모형이 없다는 것을 처치-튜링 명제를 통해 추측할 수 있다. 튜링 기계 이상의 기능을 갖는 계산 모형들이 많이 제안되었지만, 대체로 비현실적이거나 비합리적인 것 같다 (아래를 참고).

튜링 기계는 계산 가능성의 한계에 대한 질문에 답할 수 있는 매우 강력한 도구이다. 그렇다면 이제 어떤 질문을 해야할 것인가? 두 가지 질문을 제시한다.

순환 열거 언어이나 순환 언어는 아닌 언어가 존재하는가?
순환 열거 언어조차 아닌 언어가 존재하는가?

[편집] 정지 문제

이 부분의 본문은 정지 문제입니다.

컴퓨터 과학에서 가장 중요한 문제들 중 하나인 정지 문제는 평소에 컴퓨터가 어떻게 다루어지는가와, 계산 가능성 이론에 대한 핵심적인 부분을 다루고 있다. 문제의 내용은 '튜링 기계와 입력이 주어져 있을때 튜링 기계가 이 입력에 대해 멈출 것인가? 아니면 영원히 멈추지 않을 것인가?'이다.

이것은 소수의 개수나 회문과 같은 단순한 문제와는 달리 튜링 기계가 다른 튜링 기계에 대한 물음에 답할 수 있도록 해야한다. 이런 동작을 하는 튜링 기계를 설계하는 것이 불가능하다는 것을 보일 수 있다. (정지 문제 참고)

사실 주어진 프로그램이 어떤 입력에 대해 정지하는지를 아는 일반적인 방법은 단순히 작동시켜보고 멈추는지를 보는 수 밖에 없다. 만일 멈춘다면 그 기계가 멈춘다는 것을 알 수 있다. 하지만 멈추지 않는다면 이 기계가 언젠가 멈출지 아닐지 알 수 없다. 정지 언어(튜링 기계와 그 기계를 멈추는 입력의 모든 순서쌍 집합)는 순환 언어가 아니다. 따라서 정지 문제는 계산 불가능 혹은 결정 불가능하다.

정지 문제의 확장으로 라이스의 정리가 있는데, 이 정리에 따르면 어떤 튜링 기계가 수락하는 언어가 자명하지 않은 성질을 가지는지 아닌지는 결정 불가능 하다.

[편집] 순환 언어를 넘어서

정지 문제에 대응되는 언어는 순환 열거 언어이다. 작동시켰을때 튜링 기계가 그 입력에 대해 멈춘다면 기계가 멈춘다는 사실을 그 시점에서 알게 되기 때문이다. 그러나 순환 열거 언어조차 아닌 언어도 존재하며, 그 예를 들 수 있다.

순환 열거 언어가 아닌 언어로는 정지 언어의 여집합(튜링 기계와 그 기계를 멈추지 않는 입력의 모든 순서쌍 집합)이 있다. 이 언어가 순환 열거 언어가 아니라는 것을 보일 것이다. 멈추는 튜링 기계를 입력으로 받으면 영원히 멈추지 않고 나머지 경우에는 항상 멈추는 튜링 기계 $M$ 이 있다고 가정하자. 그러면 시분할 기법을 이용하여 튜링 기계를 입력으로 하여 $M$ 을 동작시키면서 동시에 입력으로 받은 기계를 동작시키는 기계 $M'$ 을 만들 수 있다. 만약 입력된 튜링 기계가 멈추지 않는다면 $M$ 이 멈추고 만일 입력된 튜링 기계가 멈춘다면 $M'$ 에서 입력으로 받은 기계를 동작시키는 부분이 멈출 것이다. 즉, $M'$ 의 두 스레드 중 적어도 하나는 멈춘다. 따라서 $M'$ 은 정지 문제를 판정할 수 있는 기계이며 이것은 정지 문제가 결정 불가능하다는데 모순이다. 따라서 정지 언어의 여집합은 순환 열거 언어가 아니다.

[편집] 가상의 계산모형

처치-튜링 명제를 통해, 튜링 기계보다 더 강력하면서 논리적인 모형은 없다고 추측할 수 있다. 그러나 비논리적인 모형은 생각할 수 있는데, 여기서 몇몇 모형을 살펴볼 것이다. 컴퓨터 과학자들은 많은 종류의 초계산기(hypercomputer)를 생각해냈다. 재귀 이론은 수리논리학의 한 갈래로 이런 계산 모형들을 엄밀하게 다룬다.

[편집] 무한실행

어떤 기계가 단계를 수행하는데 전 단계의 반만큼의 실행 시간이 걸린다고 하자. 만일 처음 단계의 실행 시간을 1이라고 둔다면 총 실행시간은

$1 + {1 \over 2} + {1 \over 4} + \cdots$

이 된다. 이 무한급수는 2로 수렴하고, 따라서 이 튜링 기계는 2의 실행 시간 내에 무한 실행이 가능하다. 이 기계는 '무한히' 실행해보는것을 통해 정지 문제를 판정할 수 있다.

[편집] 신탁 기계

이 부분의 본문은 신탁 기계입니다.

신탁 기계는 결정 불가능한 문제를 풀어내는 특정한 '신탁'에 접속할 수 있다. 예를 들어 '정지 신탁'을 가진 튜링 기계는 임의의 튜링 기계와 입력에 대해 정지 문제를 바로 판정할 수 있다.

[편집] 초월계산의 한계

이런 기계들이 기존의 한계를 벗어난 것처럼 보여도 다시 각각의 한계를 찾을 수 있다. 이런 기계들이 튜링 기계에 대한 정지 문제를 판정할 수는 있지만 그 기계들 사이의 정지 문제는 결정 불가능하다. 예를 들어 신탁 기계는 임의의 신탁 기계가 멈추는지 아닌지를 판정할 수 없다.

[편집] 계산가능성 이론의 역사

계산가능성 이론은 일차 논리에 그 뿌리를 두고 있으며, 정지 문제 및 재귀와 관련된 많은 문제들은 불완전성 정리와 밀접하게 연관되어 있다. 다비드 힐베르트와 쿠르트 괴델은 일차논리의 기초를 쌓았다. 계산가능성 이론에 앞서 알론조 처치와 스티븐 콜 클리네는 람다 셈법을 연구했다. 앨런 튜링은 현대 전산학의 아버지라 불릴 수 있을 정도로 계산 가능성 이론과 복잡도 이론의 중대한 기틀을 다졌다. 튜링의 가장 유명한 업적은 튜링 기계를 제안하여 판정 문제를 해결한 것이다.

[편집] 같이 보기

오토마타 이론
추상 기계
결정 불가능한 문제 목록
계산 복잡도 이론
계산 가능성 논리
계산 가능성 이론의 주요 논문

[편집] 참고 문헌

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.

v · d · e 컴퓨터 과학의 주요 분야
수학적 기초	수리논리학 · 집합론 · 정수론 · 그래프 이론 · 형 이론 · 범주론 · 수치해석
계산 이론	오토마타 이론 · 계산 가능성 이론 · 계산 복잡도 이론 · 양자 계산 이론
알고리즘 & 자료 구조	알고리즘 · 자료구조 · 계산 기하학
프로그래밍 언어 & 컴파일러	구문 분석 · 컴파일러 · 인터프리터 · 프로그래밍 언어 · 구조적 프로그래밍 · 객체지향 프로그래밍
병행,병렬 & 분산 시스템	병행 컴퓨팅 · 분산 컴퓨팅 · 병렬 컴퓨팅 · 그리드 컴퓨팅
소프트웨어 공학	요구 분석 · 소프트웨어 설계 · 컴퓨터 프로그래밍 · 형식수법 · 소프트웨어 테스팅 · 소프트웨어 개발
시스템 아키텍처	컴퓨터 아키텍처 · 마이크로아키텍처 · 운영체계
통신 & 네트워크	컴퓨터 오디오 · 라우팅 · 네트워크 토플로지 · 암호학
데이터베이스	데이터 마이닝 · RDBMS · SQL
인공 지능	자동추론 · 전산언어학 · 컴퓨터 비전 · 진화연산 · 기계학습 · 자연언어 처리 · 로봇학
컴퓨터 그래픽	시각화 · 영상 처리
인간과 컴퓨터 상호 작용	Computer accessibility · 사용자 인터페이스 · 착용 컴퓨터 · 유비쿼터스 컴퓨팅 · 가상현실
계산과학	인공생명 · 생물정보학 · 인지과학 · 계산화학 · 계산론적 신경과학 · 계산물리학 · 수치해석 · Symbolic mathematics

분류: 계산 이론

See also ebooksgratis.com: no banners, no cookies, totally FREE.