Entscheidungsproblem

 

만일 우리에게 어떤 논리기계가 있어서 그 안에 이런 종류의 진술들을 집어 넣고 손잡이를 돌려서, 그 논변이 논리적으로 타당한지 여부를 그 기계가 확정적으로 우리에게 말해준다면 이 얼마나 멋진 일이겠는가. 이러한 기계를 논리학자들은 결정절차 (decision procedure) 라고 한다. 바로 이러한 절차에 대한 연구가 1930 년대에 영국의 수학자 Alan Turing 으로 하여금 계산 (Computation) 의 기초를 탐구하도록 촉발시킨 계기가 되었다........ 튜링으로 하여금 지금은 튜링기계 (Turing Machine) 라고 이름붙인 이론적인 기계장치를 고안하도록 한 것이 바로 결정문제 (영어로는 decision problem, 독어로는 Entscheidungsproblem) 이다 ......... (Rudy Rucker 1988)

Entscheidungsproblem 는 주어진 일차논리 (first order) 문장이 유효한지 (universally valid) 아닌지를 결정하는 (decide) 범용 알고리즘을 발견하려고 하는, 기호논리학 (Symbolic Logic) 분야의 과제이다. 1936 년에 Alonzo Church 와 Alan Turing 은 각각의 연구에서 이것이 불가능하다는 것을 보여줬다. 마찬가지로, 특히 산술에서의 문장이 참인지 거짓인지 여부를 알고리즘적으로 결정하는 것은 불가능하다.

그러한 의문은 17 세기의 Gottfried Leibnitz 부터 시작되었는데, 그것은 수학문장의 진리값을 결정하기 위해 기호를 조작할 수 있는 기계를 꿈꾸면서, 기계적 계산기를 만드는데 성공한 직후이다. 그는 그 첫단계가 명확한 형식언어 (Formal Language) 이어야만 한다는 것이고 그의 계속 진행된 대부분의 작업이 그 목표를 향한 것이다. 1928 년에 David Hilbert 와 Ackermann 은 위에서 언급한 형식으로 문제를 제기했다.

어떤 first-order 문장이 일차 술어계산 (First order predicate calculus) 의 공리 (Axiom) 를 따른다면 유효하다 (universally valid or logically valid) 라고 할 수 있다. Kurt Gödel 의 완전성정리 (Completeness Theorem) 에서는 하나의 문장이 어떤 모델에서 그 공식 (formula)를 모두 해석하였을 때 참이라면, 그러한 경우에만 유효하다 (universally valid) 라고 하였다.

그 질문에 답하기 전에, "알고리즘 (Algorithm)" 이라는 것이 형식적으로 정의되어야 한다. 이것은 1936 년에 Alonzo Church 가 람다 계산법 (Lambda Calculus) 에 기초해서 효과적인 계산가능성 (effective calculability) 라는 개념으로 정의하였고, Alan Turing 은 같은 해에 튜링기계 (Turing Machine) 의 개념으로 정의하였다. 두 접근방법은 처치-튜링 명제 (Church-Turing Thesis) 의 예로서, 같은 것이다.

Entscheidungsproblem 에 대한 부정적인 답변이 1936 년에 Alonzo Church 에 의해, 그 직후에 Alan Turing 에 의해 행해졌다. Church 는 두 개의 주어진 lambda calculus expressions 이 같은지 다른지를 결정해주는 알고리즘은 존재하지 않는다고 증명했다. 그는 주로 Kleene 의 초기 저작에 의존했다. Turing 은 그 문제를 Turing machine 에서의 정지문제 (Halting Problem) 으로 축소시켰으며 그의 논문은 Church 의 논문보다 훨씬 더 큰 영향을 미친 것으로 생각된다. 두사람의 작업은 Kurt Gödel 의 불완전성 정리 (Incompleteness Theorem) 에 대한 초기 저작에 크게 영향을 받은 것이며, 특히 논리를 산술로 축소시키기 위해 숫자들을 논리적 공식에 할당하는 방법에 영향을 받았다.

Turing 의 주장을 따라가보자. first order logic 을 위한 일반적인 결정 알고리즘을 가졌다고 해보자. 주어진 Turing machine 이 정지하는지 않는지에 대한 의문은 결정 알고리즘에 민감한지 아닌지 하는 first-order 문장에 달렸다고 할 수 있다. 그러나 Turing 은 주어진 Turing machine 이 정지하는지 여부를 결정할 수 있는 어떤 알고리즘도 존재하지 않는다는 것을 증명했다.

만일 우리 스스로 specified object constants, function constants, predicate constants, subject axioms 을 가진 특별한 first-order 이론에 국한한다면, 그 이론에서의 문장의 참 거짓은 산술적으로 매우 잘 결정될 수 있을 것이라는 것이 중요하다. 이것의 예가 Presburger arithmetic 에 주어진다.

그러나 Peano's axioms 에 표현된 natural numbers 의 일반적인 first-order 이론은 그런 알고리즘으로는 결정될 수 없다. 이것은 위에서 언급한 Turing 의 주장으로부터 나온다. .............. (Wikipedia : Entscheidungsproblem)

다음 표에서는 계산가능성 이론 (Computability Theory) (청색) 과 계산복잡도이론 (Computational Complexity Theory) (녹색) 에서 고려되는 문제들 (또는 언어, 문법들) 을 분류하는 일부를 보여준다. 만일 문제 X 가 Y 의 진부분집합 이라면 X 는 Y 의 아래에 위치하고 검은색 선으로 연결된다. 만일 X 가 부분집합이지만 같은 집합 (equal sets) 인지도 모를 때는 점선으로 연결된다.  

 

Decision Problem

 

 

 

SolidLine.png

 

SolidLine.png

 

 

Type 0 (Recursively enumerable)

 

Undecidable

SolidLine.png

 

 

 

 

 

Decidable

 

 

 

 

 

SolidLine.png

 

 

 

 

 

EXPSPACE

 

 

 

 

 

DottedLine.png

 

 

 

 

 

EXPTIME

 

 

 

 

 

DottedLine.png

 

 

 

 

 

PSPACE

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

Type 1 (Context-sensitive)

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

PSPACE-Complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

Co-NP

DottedLine.png

 

NP

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

SolidLine.png

SolidLine.png

DottedLine.png

BPP

 

BQP

 

NP-complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

P

SolidLine.png

SolidLine.png

DottedLine.png

 

DottedLine.png

SolidLine.png

NC

 

P-Complete

SolidLine.png

SolidLine.png

 

 

 

 

 

Type 2 (Context-free)

 

 

 

 

 

SolidLine.png

 

 

 

 

 

Type 3 (Regular)

 

 

 

 

 

 

term :

튜링기계 (Turing Machine)   튜링 테스트 (Turing Test)   튜링 명제 (Turing Thesis)   계산가능성 이론 (Computability Theory)   계산 (Computation)   계산복잡도이론 (Computational Complexity Theory)

paper :

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

알고리즘과 튜링 기계 : Roger Penrose