| [ PhilosophyThought ] in KIDS 글 쓴 이(By): eulia (수선화애인) 날 짜 (Date): 1998년 6월 17일 수요일 오후 04시 09분 13초 제 목(Title): Re: 질문] Turing Computable Function에 우선 두서없는 질문에 죄송하고, 대답해주신데 대해서 감사드립니다. 또한 질문에 앞서 제가 이분야에 문외한 임을 말씀드리며 상세한 답볍을 기대하겠습니다. ----------------- "임의의 제약을 지니는 시스템(이하 A)이 Turing-Computable"이라고 증명되었을때, A는 적어도 functionally Turing-Computable function의 class에 포함되는 behavior들을 수행하게 될겁니다. 따라서 제가 궁금했던것은 시스템의 특성, 즉 어떤 제약이(예를 들어 non-determinism과 같은 behavioral 특성) Turing Machine상에서의 Computability에 영향을 주는가?, 하는 것입니다. 제가 관심을 가지고 있는 시스템은 "임의의 특성을 지닌 회로 Class"(이하 C) 입니다. 저는 제 직감에 C가 Turing Computable하지 않은 function을 포함하고 있다고 했을때, 그 이유로 회로 Class C가 non-determinism의 특성을 가지고 있기 때문이라고 일단을 생각을 했습니다. 즉 Turing Computable function Class에는 non-determinism을 지닌 함수가 없다는 생각이죠. 그러나 이상하게도 제가 아는 지식에서는 기본적인 FA나 NFA(Non-deterministic FA)만을 보더라도 이 둘이 equivalence 관계에 있으니, 제가 앞부분에서 말한 non-determinism도 여기에 와서 결국은 FA와 같은 class에 포함되게 됩니다. 결국 Non-determinism은 Turing Computable Function Class에 속한 함수가 가질수 있는 특성이 되버립니다. 또한 윗 게스트님의 답글 Turing Computable Function을 "직관적으로 계산하는 알고리즘을 줄수 있겠다고 생각하는 바로 그 함수들"이라고 말씀하셨는데, 일단 '직관적'이라는 말의 의미를 이해하기가 어렵군요. 또한 위의 게스트님께 한가지 여쭙고 싶은것은 그럼 과연 "임의의 random 수를 생성하는 알고리즘"은 Turing Computable Function Class에 속하게 되는 겁니까?. 이와 같은 질문은 non-determinism이 바로 위의 random 수의 성생 알고리즘에 의해서 구현될수 있기 때문입니다. 그러나 제가 알기로는 Perfect한 random 수의 생성 알고리즘은 존재하지 않는것으로 알고 있습니다. 왜냐하면 임의의 계산절차와 seed는 결국에는 같은 random수를 생성하기 때문이죠. 따라서 이러한 이유로 non determinism이란 system의 behavior는 Turing Computable Function과 그렇지 못한 함수를 구불할수 있는 부분적인 criteria가 되지 않나 하는 생각입니다. 이외에 어떤 characteristic criteria가 존재할수 있겠습니까? ----------------------------------------------------- 위의 제생각에 대한 '옳고 그름'의 문제와 몇가지 질문에 대해서 답변을 부탁드립니다. 감사합니다. 문외한 ... ---------------------------------------------------------------------------- A : 뭘 그렇게 생각하니 ? 어떤꽃인지아직도보지못했다. 정근 : 나 ... 난 말이지, 난, 나는 ... 봄에만살짝피었다지는꽃. *** 수선화 애인 *** 어떤꽃일까 ? ---------------------------------------------------------------------------- |