12. 26

• 어젯밤 SEP의 <Turing Machines> 항목을 재미있게 읽었다. 철학 백과라고 이름을 달고 있는데도 컴퓨터 과학에 대해 이렇게까지 자세하게 쓰이다니! SEP는 내가 생각하는 철학에 대한 의무에 놀랍도록 충실하다. Zombie항목부터 시작해서 컴퓨터 과학의 첨단까지, 인간의 존재론을 흔들 수 있는 모든 다양한 주제들에 대해서 철학적 견해를 들을 수 있다. 심지어 레퍼런스도 빵빵하다.. 이 항목에서 흥미롭게 읽은 몇가지.
• (1) Turing Machine은 특별한 기기라기보다, 컴퓨터의 수학적 모델링으로, 그것도 무한한 수행시간과 무한한 메모리가 주어진 이데아적인 개념이라고 볼 수 있다. 여기서 Turing Computability라는 개념이 나오는데, 알고리즘 수행에 대한 시간/공간개념을 추상해 버렸으므로 굉장히 넓은 개념이다. 반대로 Turing Uncomputable한 함수는 정말 강력한 개념으로.. 영원히 계산하지 못하는 함수라고 할 수 있다.
• (2) 무한한 시간과 공간이 주어졌는데도 계산하지 못하는 함수가 있나?싶지만, 있다. 항목에서는 두 가지가 소개되는데, 하나는 Busy Beaver에 관한 함수, 다른 하나는 다른 함수의 Halting여부를 반환하는 함수이다. 둘다 귀류법으로 증명된다.