Mathematics  : Definition

• 유효한 결론을 이끌어내는 형식적 규칙이란 무엇인가? (logic)
• 계산될 수 있는 것은 무엇인가? (computation)
• 인간은 불확실한 정보를 가지고 어떻게 추론하는가? (probability)

철학자들이 인공지능 (Artificial Intelligence) 의 대부분의 중요한 아이디어를 명확히 하였지만, 형식과학 (formal science) 으로의 도약은 3 개의 기본 영역, 즉 논리 (Logic), 계산 (Computation), 확률 (Probability) 에서의 수학적 형식화를 필요로 했다.

형식논리의 개념은 고대 그리스의 철학자로 거슬러 올라갈 수 있지만, 그 수학적 개발은 사실상 George Boole (1815~1846) 이 자세히 묘사한 명제논리 (Propositional Logic) (또는 Boolean logic, Boole 1847) 과 함께 시작하였다. 1879 년에 Gottlob Frege (1848~1925) 는 Boole's logic 을 확장하여 객체 (objects) 와 관계 (relations) 을 포함한 일차논리 (First-order Logic) 을 창조하여 오늘날에는 가장 기본적인 지시표현 시스템이 되었다. Alfred Tarski (1902~1983) 는 theory of reference 를 소개하여 논리속의 객체가 실세계의 객체와 어떻게 관계하는지를 보여주었다. 다음 단계는 logic 과 computation 으로서 할 수 있는 것의 한계를 결정하는 것이었다.

최초의 증명된 (nontrivial) 알고리즘은 최대공약수를 계산하는 Euclid 알고리즘 으로 알려져있다. 알고리즘 (Algorithm) 이란 말은 9 세기 페르시아 수학자 al-Khowarazmi 가 유럽에 아라비아 숫자와 대수 (algebra) 를 소개하면서 나온 말이다. Boole 과 여러사람들이 논리적 연역법 (Deduction) 을 위한 알고리즘을 연구했고, 19 세기말 까지 일반적 수학추론 (mathematical reasoning) 을 논리적 연역법으로 형식화하는 작업을 수행했다.

1900 년에 David Hilbert (1862~1943) 는 그가 정확하게 예상한 23 개의 문제 리스트를 소개하여 20 세기에 수학자들이 공유하게 했다. 마지막 문제는, 자연수를 포함하는 어떤 논리적 명제의 진위여부를 결정하는 알고리즘이 있는지 여부를 질문하는 유명한 판정문제 (Entscheidungsproblem 또는 decision problem) 이다. 기본적으로 Hilbert 는 효율적인 (effective) 증명절차의 능력에 근본적인 한계가 있는지를 질문하는 것이었다. 1930 년에 Kurt Gödel (1906~1978) 은 Frege 와 Russell 의 일차논리 (First-order Logic) 으로 어떤 진리 문장 (true statement) 을 증명하는 효율적인 절차가 존재하지만, 그러나 first-order logic 은 자연수를 특징짓는데 필요한 수학적 귀납법 (Mathematical Induction) 의 원칙을 포착할 수는 없었다는 것을 보여주었다. 1931 년에 그는 실제적인 한계가 존재한다는 것을 보여주었다. 그의 불완전성 정리 (Incompleteness Theorem) 에서, 자연수의 속성을 충분히 묘사하는 어떤 언어에서, 그 진리여부가 어떤 알고리즘에 의해 결정될 수 없다는 의미에서 결정불가능한 (undecidable) 진리 문장이 존재한다는 것을 보여주었다.

이러한 근본적인 결과는 알고리즘으로 표현될 수 없는 정수에 기초한 함수 (some functions on the integers) 가 있는지 - 즉 그것이 컴퓨터 (Computer) 로 계산가능한지를 보여주는 것으로 해석될 수 있다.  이것이 Alan Turing (1912~1954) 이 그 함수들이 컴퓨터로 계산가능하다 라고 정확하게 정의하려고 노력한 계기가 되었다 (계산가능성 이론 (Computability Theory)). 이러한 개념은 실제로는 다소 의심스러운 것이었다. 왜냐하면 계산 (computation) 이나 효율적인 (effective) 절차의 개념은 사실은 형식적인 정의를 할 수가 없었기 때문이다. 그러나 튜링 기계 (Turing Machine) (Turing 1936) 는 어떤 계산가능한 함수도 계산할 수 있다고 서술한 처치-튜링 명제 (Church-Turing Thesis) 는 충분한 정의를 제공한 것으로 일반적으로 받아들여졌다. Turing 은 또한 어떠한 튜링기계도 계산할 수 없는 함수들이 존재한다는 것을 보여주었다. 예를들면, 어떤 기계도 주어진 프로그램이 주어진 입력에 대해 하나의 대답을 리턴할 것인지, 영원히 작동할 것인지를 일반적으로 (in general) 말할 수 없다 (정지문제 (Halting Problem)).

비록 결정불가능성 (undecidability) 와 계산불가능성 (noncomputability) 이 계산의 이해에 중요하지만, 다루기어려움 (intractability) 라는 개념은 훨씬 더 큰 의미를 가지고 있다. 대강 얘기하자면, 문제를 해결하기 위해 필요한 시간이 문제의 크기에 따라 지수적으로 (exponential) 증가한다면 그 문제는 난해 (intractable) 하다고 한다. 복잡성 (Complexity) 에서의 다항식과 지수적 (polynomial and exponential) 증가 사이의 차이는 1960 년대 중반에 처음 강조되었다 (Cobham 1964 ; Edmonds 1965). 지수적인 증가는 다소 큰 문제 조차도 이성적인 시간내에 풀릴 수 없다는 것을 의미하기 때문에 중요하다. 따라서 지능적인 행동을 생성하는 난해한 (intractable) 전체문제를 다루기쉬운 (tractable) 하위문제들로 나누어서 해결하려 해야 한다.

난해한 문제 (intractable problem) 인지 아닌지를 어떻게 인식할 수 있는가? Stephen Cook (1971) 과 Richard Karp (1972) 가 개척한 비결정 완전 (NP-complete) 이론은 하나의 방법을 제공한다. Cook 과 Karp 는 NP-complete 인 문제들, 즉 표준이 되는 조합탐색 (combinatorial search) 와 추론 (Reasoning) 문제를 크게 분류해 놓은 것 (표) 을 보여주었다. NP-complete 의 분류 (표) 로 환원될 수 있는 어떠한 문제도 intractable 일 것이다. (비록 NP-complete 문제들이 반드시 intractable 하다고 증명되지는 않았지만 대부분의 이론가들이 그것을 믿는다). 이러한 결과는 대중언론에서 최초의 컴퓨터를 "아인슈타인보다 더 빠른!" "전자 슈퍼 두뇌 (super-brain)" 이라며 환영했었던 낙관론과는 상반되는 것이다. 컴퓨터 (Computer) 의 속도가 점점 증가함에도 불구하고, 자원들을 주의깊게 사용해야만 지능적 시스템이 가능하게 될 것이다. 거칠게 보자면, 세계는 극단적으로 (extremely) 큰 문제의 사례 (instance) 인 것이다!  최근의 몇 년사이에 AI 는 NP-complete 문제의 사례 (instance) 들이 왜 어려운지 (hard), 그러나 다른 것들은 쉬운지 (easy) 를 설명하는데 도움을 주었다 (Cheeseman et al 1991).

논리와 계산이외에, 수학 (Mathematics) 이 AI 에 공헌한 세 번째는 확률 (Probability) 이론이다. 이탈리아인 Gerolamo Cardano (1501~1576) 가 최초로 확률 개념의 틀을 잡았는데, 도박사건 (gambling events) 에서 가능한 결과의 의미로 확률을 묘사했다. 확률은 빠르게 모든 계량과학 (quantitative science) 에서 매우 중요한 부분이 되었으며, 불확실성 측정과 불완전한 이론을 다루는데 도움을 주었다. Pierre Fermat (1601~1665), Blaise Pascal (1623~1662), James Bernoulli (1654~1705), Pierre Laplace (1749~1827) 외 여러사람이 그 이론을 발전시켰고 새로운 통계적 방법을 소개했다. Thomas Bayes (1702~1761) 는 새로운 증거가 나타났을 때 기존의 확률을 업데이트하는 규칙을 제안했다. Bayes'rule 과 그 결과로 등장한 베이즈 해석 (Bayesian analysis) 분야는 인공지능 (Artificial Intelligence) 시스템에서 불확실성 (Uncertainty) 추론을 할 때 가장 현대적인 접근방법의 기초를 형성하게 된다. ................. (Stuart Russell  Peter Norvig 2003)

수학은 기호논리와 수학표기를 사용해서 공리적으로 정의된 추상구조 (axiomatically defined abstract structures) 를 조사하는 것이다. 수학은 흔히 구조, 변화, 공간의 패턴에 대한 학문이라고 정의된다 ; 형식을 갖추지 않고 말하자면 "그림과 수 (figures and numbers)" 에 대한 학문이다. 수학은 실험에 근거를 둔것은 아니기 때문에 (not empirical) 과학과는 다른것이다. 수학적 지식은 연구와 응용을 통해 계속적으로 증가한다. 수학의 발달이 반드시 과학에서 응용되는 것은 아닐지라도, 수학은 보통 과학을 위한 tool 로 간주된다. ........... (Wikipedia : Mathematics)