튜링 동치(Turing equivalence)

                                                                                                                                                         

                                                                                                                                                                                                                   

                                                                                                                                                         

                                                                                                                                                                                                              

                                                                                                                                                                                                              

  

만일 컴퓨터 P와 Q가 있을 때, P가 할 수 있는 일을 Q가 모두 흉내(simulate)낼 수 있고, Q가 할 수 있는 일을 모두 P가 흉내낼 수 있다면 두 컴퓨터는 튜링 동치이다. 대표적인 예가 세마포어와 뮤텍스(Mutual Exclusion)이다. 세마포어로 뮤텍스를 구현할 수 있고, 뮤텍스로 세마포어를 구현할 수 있기 때문에 두 기능은 동치이다.

---

Reference

• https://namu.wiki/w/튜링 머신