Computability  Theory

 

계산가능성 이론은 어떤 문제를 알고리즘 (또는 Turing Machine) 으로 해결할 수 있는가 (다양한 제약과 확장이 있는 가운데서) 를 다루는 계산이론 (Theory of Computation) 의 일부분이다. 그것은 4 개의 주요한 의문을 제기한다 :

계산이론 (Theory of Computation) 에서는 문제들의 부류가 다른 부류의 부분집합인 관계를 보여주는 chart 를 볼 수 있다.

어떤 문제를 Turing machine 이 해결할 수 있는가?

어떤 문제도 해결할 수 없다. 결정불가능성 (undecidable) 문제는, 무제한의 시간과 메모리가 주어지더라도 ,어떤 알고리즘으로도 풀 수 없는 것이다. 많은 결정불가능성 문제들이 알려져 있다. 예를들면 결정문제 (Entscheidungsproblem) (독일어로 'decision problem') 가 그것이다. 즉 일차 술어계산 (First order predicate calculus) 의 문장이 주어졌을 때 그것이 유효한지 (universally valid) 여부를 결정하는 문제이다. Alonzo Church 와 Alan Turing 은 각각 그것이 결정불가능하다고 증명했다. 정지문제 (Halting Problem) 는 하나의 프로그램과 그것에 대한 입력이 주어졌을 때 그것이 영원히 작동할 것인지 정지할 것인지를 결정하는 문제이다. Turing 은 그것도 또한 결정불가능하다고 증명했다. 그는 계산가능한 수 (computable number) 라고 하는 것은 n 이 주어졌을 때 n 번째 숫자를 계산하는 알고리즘이 있는 실수라고 정의했다 (a real number for which there is an algorithm that, given n, calculates the nth digit). 그는 거의 모든 수는 계산불가능 (uncomputable) 하다고 증명했다. Chaitins constant 는 비록 잘 정의되었더라도 계산불가능한 수이다.

어떤 다른 시스템이 Turing machine 과 동등한가?

Turing machine 에 의해 받아들여진 언어는 formal grammars 에 의해 생성된 바로 그것이다. Lambda calculus 는 함수를 정의하는 한 방법이다. Lambda calculus 로 계산될 수 있는 함수는 Turing machine 에 의해 계산될 수 있는 바로 그것이다. 3 가지 형식, 즉 Turing machine, formal grammars, lambda calculus 는 전부 매우 다른 것처럼 보이고, 다른 사람들이 개발한 것이다. 그러나 그것들은 전부 동등한 것이며 같은 문제해결 능력을 가진다. 이것은 대개 알고리즘이나 효율적인 과정에 대한 우리들의 직관적인 언급은 Turing machine 의 수학적 정의로 포착된다고 주장하는 처치-튜링 명제 (Church-Turing Thesis) 의 증거로서 취급된다.

만일 무제한 양의 메모리 접근이 가능하다면, 전자컴퓨터 심지어는 양자컴퓨터 (quantum computer) 조차도 Turing machine 과 정확히 동등하다. 결론적으로 모든 구현가능한 프로그래밍 언어들은 기껏해야 Turing machine 의 능력과 동등하다 (실제로는 능력이 떨어진다). 그러한 언어들은 Turing-complete 하다고 한다. Turing machine 과 동등한 시스템들은 다음과 같다 :

마지막 세 개의 예는 언어를 받아들이는 (accepting) 다소 다른 정의를 사용한다. 즉  만일 어떤 (any) 계산이 non-deterministic 을 받아들이거나, 대부분의 (most) 계산이 probabilistic and quantum 을 받아들인다면 문자열 (string) 을 받아들인다고 할 수 있다. 이러한 정의가 주어진다면 이러한 기계들은 언어를 받아들이기 위한 Turing machine 과 같은 능력을 가진다.  

어떤 문제들이 더 강력한 기계들을 필요로 하는가?

어떤 기계들은 Turing machine 보다 더 강력하다고 생각된다. 예를들면 oracle machine 은 통상의 Turing machine 에서는 가능하지 않은 특수한 함수를 계산할 수 있는 블랙박스를 사용한다. theory of real computation 은 infinite-precision real numbers 를 사용하는 기계를 다룬다. 이 이론에서는 " complement of the Mandelbrot set 은 부분적으로는 결정가능하다" 와 같은 흥미로운 문장을 증명하는 것이 가능하다 (hypercomputation).

어떤 문제들이 덜 강력한 기계로도 풀릴 수 있는가?

촘스키 계층 (Chomsky Hierarchy) 는 4 부류의 알고리즘으로 받아들일 수 있는 언어를 정의한다. 그들은 모두 기계가 어떤 형태의 메모리와 결합된 non-deterministic finite state machine 로 구성된다고 가정한다. 만일 메모리가 무한 테이프라면 Turing machine 은 full power 를 가지며, unrestricted grammars 에 의해 생성된 언어를 정확히 받아들일 수 있다. 만일 입력의 크기와 비례하는 메모리만 주어진다면, 문맥인식 문법 (Context Sensitive Grammar) 에 의해 생성된 언어를 정확히 인식할 수 있다. 만일 메모리로서 하나의 stack 만 주어진다면, 문맥자유 문법 (Context Free Grammar) 에 의해 생성된 언어를 정확히 인식할 수 있다. 만일 어떠한 추가의 메모리도 주어지지 않는다면 regular grammars 에 의해 생성된 언어를 정확히 받아들일 수 있다.

메모리나 시간, 또는 다른 자원에 대한 제약이 고려될 때가 있다. 이러한 제약의 결과는 computability theory 보다는 계산 복잡도 이론 (Computational Complexity Theory) 의 일부로서 보통 고려된다. .......... (Wikipedia : Computability Theory)

paper :

계산가능성과 심적과정 : Philip N. Johnson-Laird

해결이 불가능한 문제들 : Rudy Rucker

계산가능성과 논리 : George S. Boolos   Richard C. Jeffrey

계산가능성 이론 형성에서의 Church's Thesis 와 Turing's Thesis : 현우식, 한국수학사학회, 1998

계산가능성과 전산적 마음 (Computability and Computable Mind) : 이영의, 고려대철학연구소, 1994

site :

Wikipedia : Computability Theory    위키백과 : 계산가능성 이론