| [ PhilosophyThought ] in KIDS 글 쓴 이(By): eulia (수선화애인) 날 짜 (Date): 1998년 6월 21일 일요일 오후 08시 19분 19초 제 목(Title): Re: 질문] Turing Computable Function에 우선 게스트님의 답변에 감사드립니다. -- 제가 질문하려고 하는 바는 Computability의 Formalism에 대해서 이야기하는 것은 아닙니다. 좀더 제가 생각하는 바를 전달하기 위해서 제가 왜 이런 문제를 생각했나를 말씀드리겠습니다. -- 기존의 회로가 Clock이라는 전역 제어신호를 사용한데 반하여, 저전력소모 및 Clock Skew라는 문제점을 해결하기위해서 전역 제어 신호인 Glock을 사용하지 않고 회로를 구현하는 Asynchronous Circuit Design Methodology에 대해서 저는 연구하고 있습니다. 동기회로의 전체시스템을 제어해주는 global clock이 없기때문에, 회로는 보다 localize되게 되고, potentialy faster한 회로를 얻을수 있습니다. 그러나 이런회로는 시스템의 delay를 고려하여 올바르게 동작하도록하는 Clock이 없기때문에, 회로의 wire와 gate의 delay를 고려하여 design 해야하며, 이러한 작업은 매우 어렵습니다. 또한 비동기회로는 wire와 gate의 delay를 어떻게 가정하는가에 따라서 크게 4가지로 구분되고, 그중에 하나인 Quasi Delay Insensitive라는 Delay가정하에는 wire와 gate의 delay를 unknown, but finite이라고 고려하게 됩니다. 단지 하나의 wire가 두개의 wire로 분리될때(Forking) 같은 속도로 신호가 분기된 두 wire를 propagation한다고 가정하게 됩니다. (이를 Isochronik Fork)라고 합니다. -- 여기서 하나의 논문 "Quasi Delay Insensitive Circuit is Turing Computable" 이라는 논문을 보게 되었습니다. 위논문에서는 CSP(Communication Sequential Process: 일반적으로 병행시스템을 기술하는 language type의 Formalism)을 이용하여 QDI Circuit의 Class를 구성한후에, 이를 다시 Turing Machine으로 변환시킴으로써 QDI Circuit의 Class에 있는 회로가 가지는 함수(function이라기 보다는 behavior라고 말하는 것이 옳바를것 같군요.)가 Turing Computable이라고 증명하였습니다. -- 위의 논문을 보고 생각한 것이 "Turing Computable하지 않은 함수", 즉 "Turing Computable이 아니면 QDI Circuit이 아니다"라는 명제에 기반하여 어떤 함수가 Turing Computable 하지 않으며, 따라서 QDI Circuit의 회로로 구성할수 없게 될까?하는 궁금점이 생기게 되었고, 결국 회로라는 의미에서 회로의 어떤 functional behavior(이를 함수라고 부를수는 없을겁니다. 이유는 회로에는 arbitor와 같이 결정적이지 않은 결과값을 생성하는 behavior를 포함하기 때문입니다.)가 Turing Computability에 영향을 주는가? 라는 질문을 이곳 kids에 올리게 되었습니다. 초기 저는 회로의 관점에서 함수를 보다보니, arbiter와 같은 기능을 "결정적인 값을 생성하는 함수"라는 정의에 포함시키게되는 오류를 범한것 같습니다. 가장 단순한 arbitor로서 두개의 입력과 두개의 출력을 가지는 arbitor는 입력 a -> 출력 p, 입력이 b -> q, 그러나 동시에 두개의 입력에 a라는 event와 b라는 event가 생성되면 어떤출력을 발생할지 모르게 됩니다. 결국 non-determinism이죠. QDI Circuit이 위와 같은 arbiter 회로를 fair하게 구현하지 못한다는 것이 증명되있습니다.(trace formalism을 이용하여...) 이러한 이유로 전 non-determinism이 Turing Computability에 영향을 주는 functional behavior가 아닌가 생각을 했던 것입니다.(잘못이란것을 게스트님의 지적으로 알게 되었죠.). ------------------- 답변에 감사드립니다. - 초보는 외로워~ p.s. 이보드의 성격상 실제적이며 구체적인 회로에 대한 이야기를 꺼내는것이 처음에 꺼려져서 단지 초기글에서 임의의 특성을 지니는 회로라고 이야기를 드렵씁니다. ---------------------------------------------------------------------------- A : 뭘 그렇게 생각하니 ? 어떤꽃인지아직도보지못했다. 정근 : 나 ... 난 말이지, 난, 나는 ... 봄에만살짝피었다지는꽃. *** 수선화 애인 *** 어떤꽃일까 ? ---------------------------------------------------------------------------- |