| [ PhilosophyThought ] in KIDS 글 쓴 이(By): guest (KFHS) 날 짜 (Date): 1998년 6월 22일 월요일 오전 12시 59분 05초 제 목(Title): Re: 질문] Turing Computable Function에 어떤 함수가 computable 하다는 말이 바로 그 함수가 [algorithmic 하게] 구현가능하다는 말입니다. 이를테면, 일반적인 계산 모델, 예컨데 lambda calculus 같은 것을 생각하면 lambda term (reduction rule 을 어떻게 잡느냐에 따라서 좀 복잡하게 달라질수 있지만 대강 얘기하면) 들은 normal form 으로 reducible 하니까 계산 가능한 함수이지만, concurrency 모델들은 이렇게 쉽게 얘기할수 없습니다. 따라서 어떤 concurrency 모델로 기술된 (대개는 process algebra 의 일종이 되겠지요.) '시스템' 이 있다고 하면 이번엔 이 '시스템' 이 꼭 계산 가능하다고 (물론 심지어 함수라고도) 확신할 수가 없습니다. 따라서 어떤 기술하고자 하는 대상을 CSP 던 Pi calculus 건 기술했다고 하면 명백한 경우가 아닌 한 이것이 computable 하다는 것을 증명할 필요가 있을 것입니다. 모든 finite process 는 computable 하다는 건 theorem 인것 같습니다만 infinite process 일 경우에는 따로 증명할 필요가 있을수도 있을 것입니다. 물론 그럴 경우 계산가능성을 증명하는 방법은 바로 우리가 아는 계산 모델로 그 대상을 환원하는 것입니다. 다른 말로 '프로그램' 하는것이 되겠지요. |