2019/04/01 정기모임 세미나 “Uncomputability of Exponential Diophantine Equation” (Speaker:김태영)

일시 : 2019. 04. 01(월) PM 9:30

ABSTRACT

컴퓨터는 무엇이든 할 수 있을까요? 전산 이론의 한 분야인 계산 가능성 이론은 컴퓨터가 할 수 없는, 즉 계산 불가능한 문제와 계산 가능한 문제에 대해 다룹니다. 이번 세미나에서는 그 중 힐베르트의 문제 중 10번째인 Diophantine Equation의 해의 존재성이 계산 불가능함을 계산 가능성 이론에서 가장 유명한 문제인 Halting Problem과의 관계를 보여 증명하였습니다. 또한 알고리즘과 문제라는 모호한 정의를 수학적으로 제대로 정의하였습니다.

선수지식 : 없음

알면 좋은 것 : Halting Problem, 기초적인 알고리즘

Posted in 세미나 and tagged .