에밀 포스트

에밀 레온 포스트(Emil Leon Post, 1897년 2월 11일 ~ 1954년 4월 21일)는 폴란드계 미국인 수학자, 논리학자이다. 계산가능성 이론 등에 공헌하였다.

생애 
포스트는 당시 러시아 제국령이던 폴란드 아우구스투프의 유대인 가정에서 태어났으며 어린 나이에 그의 가족이 뉴욕시로 이사하였다. 어린 시절 포스트는 천문학에 관심이 많았으나 12세에 자동차 사고로 왼팔을 잃은 이후 수학에 치중하게 되었다.

고등학교 졸업 후 뉴욕 시티 칼리지에 입학하여 수학을 공부하고 1917년 졸업한다. 1920년 컬럼비아 대학에서 캐시어스 잭슨 키저(Cassius Jackson Keyser)의 지도 하에 수학 박사 학위를 취득한다. 곧 프린스턴 대학에 박사후연구원으로 들어갔다가 1921년부터는 고등학교 수학 교사로 일하게 된다. 프린스턴 재직 시절부터 심한 조울증 증세를 보여 연구에 지장을 겪었다고 한다.

1936년에는 뉴욕 시티 칼리지의 수학과 교수로 임용되었다. 1954년 우울증에 대한 전기 충격 치료를 받고 심장마비로 사망하였다.

업적 
포스트는 그의 박사 논문에서 수학 원리의 명제 연산의 완전성을 증명하였다. 또한 루트비히 비트겐슈타인 및 찰스 샌더스 퍼스와는 독립적으로 진리표 기법을 도입하였다. 특히 프린스턴에 재직 중이던 때에는 (쿠르트 괴델이 1931년 증명한) 수학원리의 불완전성의 증명에 근접하였으나 스스로 확신이 들지 않아 출판하지 않았다. 이러한 그의 업적들은 당시에는 주목받지 못하다가 나중에야 발견되었다.

한편 앨런 튜링의 튜링 기계 연구와 독립적으로 튜링 기계와 동등한 계산 모델을 고안하였으며, 그의 논문 Formulation 1에서 고안된 이 계산 모델은 포스트-튜링 기계로 불린다.

1944년 계산불가능한 재귀 열거 집합이면서 그 튜링 차수가 정지 문제의 튜링 차수보다 작은 경우가 존재하겠는가 하는 문제를 제기하였고, 이는 튜링 차수 연구에서 중요한 '포스트의 문제'로 불리게 된다. 이는 1950년대 재귀 이론의 강력한 기법인 priority method가 도입되면서 긍정으로 해결되었다.

1946년에는 결정불가능한 결정 문제의 간단한 예시로서 포스트 대응 문제(Post correspondence problem)를 제시하였다. 이외에 미분의 일반화(generalized differentiation)에 관한 유명한 논문을 썼으며, 보편 대수학에 관한 긴 논문에서 다진군(polyadic group)에 대한 여러 중요한 결과를 보이기도 했다.

같이 보기 
 계산가능성 이론
 산술 위계

각주 

1897년 출생
1954년 사망
유대계 폴란드인
폴란드계 미국인
미국의 논리학자
수리논리학자
조울증 환자
뉴욕 시립 대학교 교수