튜링1 튜링 동치(Turing equivalence) 만일 컴퓨터 P와 Q가 있을 때, P가 할 수 있는 일을 Q가 모두 흉내(simulate)낼 수 있고, Q가 할 수 있는 일을 모두 P가 흉내낼 수 있다면 두 컴퓨터는 튜링 동치이다. 대표적인 예가 세마포어와 뮤텍스(Mutual Exclusion)이다. 세마포어로 뮤텍스를 구현할 수 있고, 뮤텍스로 세마포어를 구현할 수 있기 때문에 두 기능은 동치이다. Reference https://namu.wiki/w/튜링 머신 2019. 12. 22. 이전 1 다음