그레고리 차이틴

1.1. 출생 및 어린 시절

그레고리 존 차이틴은 1947년 6월 25일에 태어난 아르헨티나계 미국인 수학자이자 컴퓨터 과학자이다. 그의 부모는 아르헨티나 출신이며, 차이틴은 어린 시절의 일부를 아르헨티나에서 보냈다. 그는 유대인 혈통을 가지고 있다.

1.2. 교육

차이틴은 미국의 명문 과학 고등학교인 브롱스 과학 고등학교를 졸업하고, 뉴욕시립대학교에 진학했다. 그는 10대 시절에 이미 콜모고로프 복잡성 이론의 기초를 독자적으로 발전시키는 등 뛰어난 학업적 재능을 보였다.

2.1. 알고리즘 정보 이론 및 콜모고로프 복잡성

차이틴은 레이 솔로모노프와 안드레이 콜모고로프와 함께 오늘날 알고리즘 정보 이론으로 알려진 분야의 창시자 중 한 명으로 여겨진다. 이 이론은 프로그램 크기 또는 콜모고로프 복잡성이라는 개념을 통해 정보의 무작위성을 측정한다. 솔로모노프, 콜모고로프, 페르 마르틴뢰프, 레오니트 레빈 등의 연구와 함께 알고리즘 정보 이론은 이론 컴퓨터 과학, 정보 이론, 수학적 논리의 기초적인 부분이 되었다.

차이틴의 정리는 충분한 산술을 표현할 수 있는 어떤 이론에서도, 특정 상한 c보다 큰 콜모고로프 복잡성을 가진 어떤 수도 그 이론 내에서 증명될 수 없다는 것을 보여준다. 이는 괴델의 불완전성 정리가 거짓말쟁이의 역설과 관련되어 있듯이, 차이틴의 결과는 베리의 역설과 관련이 있다.

2.2. 차이틴 상수 (Ω)

차이틴은 차이틴 상수 Ω를 정의했다. 이 상수는 정규수의 특성을 가지며, 비형식적으로는 임의의 프로그램이 중단될 확률을 나타내는 표현으로 설명되기도 한다. Ω는 정의 가능수이지만 계산 불가능한 수라는 수학적 속성을 지닌다. 즉, 아래로부터의 점근적 근사는 가능하지만 위로부터의 근사는 불가능하다.

2.3. 메타수학 및 불완전성

차이틴은 메타수학 분야에서도 중요한 기여를 했다. 그는 자신의 연구가 괴델의 불완전성 정리와 유사한 컴퓨터 이론적 결과를 보여주며, 이는 "이유 없이 참인, 우연히 참인 수학적 사실"이 존재한다는 것을 시사한다고 주장한다. 이러한 주장은 수학의 인식론적 측면에 대한 그의 통찰을 보여준다. 차이틴은 수학자들이 이러한 수학적 사실을 증명하려는 희망을 버리고, 준경험주의적 방법론을 채택해야 한다고 제안한다.

2.4. 알고리즘 및 컴파일러 최적화

차이틴은 컴파일러에서 레지스터 할당을 수행하기 위해 그래프 색칠 기법을 사용하는 아이디어를 처음 제시했다. 이 과정은 '차이틴 알고리즘'으로 알려져 있으며, 컴퓨터 과학 분야에서 실제적인 응용을 통해 컴파일러 최적화에 기여했다.

3.1. 디지털 철학

차이틴은 '디지털 철학'이라는 입장을 옹호한다. 이는 우주와 실재를 정보와 계산의 관점에서 해석하는 형이상학적 주장이다. 그는 알고리즘 정보 이론이 생물학(생명의 공식적 정의, 기원, 진화)과 신경과학(의식 문제 및 마음 연구) 분야의 문제들을 해결하는 열쇠라고 주장한다.

3.2. 수학적 사실의 본질과 한계

수학의 인식론에 있어 차이틴은 자신의 수학적 논리 및 알고리즘 정보 이론 연구를 바탕으로 "이유 없이 참인, 우연히 참인 수학적 사실"이 존재한다는 철학적 입장을 옹호한다. 그는 이러한 사실들을 증명하려는 전통적인 수학적 접근 방식의 한계를 지적하며, 대신 수학자들이 준경험주의적 방법론을 채택해야 한다고 제안한다.

3.3. 생물학 및 진화론에 대한 접근

차이틴은 생명의 정의, 기원, 진화 과정을 정보 이론적으로 설명하려는 시도를 통해 메타생물학 분야에 관심을 가지고 있다. 그는 생명을 '진화하는 소프트웨어'로 간주하며, 진화론을 정보 이론적으로 형식화하는 데 관심을 기울이고 있다.

4.1. 연구 활동

차이틴은 과거 IBM의 토머스 J. 왓슨 연구소에서 연구원으로 재직했으며, 현재도 명예 연구원으로 남아 있다. 그는 또한 모하메드 6세 폴리테크닉 대학교의 고등 연구원(Institute for Advanced Studies)의 일원이다.

4.2. 학계 활동

차이틴은 리우데자네이루 연방대학교에서 교수로 재직하며 학문적 활동을 이어갔다.

6.1. 주요 저서

• Information, Randomness & Incompleteness (World Scientific, 1987)
• Algorithmic Information Theory (Cambridge University Press, 1987)
• Information-theoretic Incompleteness (World Scientific, 1992)
• The Limits of Mathematics (Springer-Verlag, 1998)
  • 한국어 번역본: 『수학의 한계』 (2001)
• The Unknowable (Springer-Verlag, 1999)
  • 한국어 번역본: 『알 수 없는 것』 (2001)
• Exploring Randomness (Springer-Verlag, 2001)
• Conversations with a Mathematician (Springer-Verlag, 2002)
  • 한국어 번역본: 『수학자와의 대화』 (2003)
• From Philosophy to Program Size (Tallinn Cybernetics Institute, 2003)
• Meta Math!: The Quest for Omega (Pantheon Books, 2005)
  • 한국어 번역본: 『메타 수학! 오메가를 찾아서』 (2007)
• Teoria algoritmica della complessità (G. Giappichelli Editore, 2006)
• Thinking about Gödel & Turing (World Scientific, 2007)
• Mathematics, Complexity and Philosophy (Editorial Midas, 2011)
• Gödel's Way (CRC Press, 2012)
• Proving Darwin: Making Biology Mathematical (Pantheon Books, 2012)
  • 한국어 번역본: 『다윈을 수학으로 증명하다』 (2014)
• Philosophical Mathematics: Infinity, Incompleteness, Irreducibility (Academia.edu, 2024)