Turing equivalent
숙어C2formal튜링 기계와 같은 계산 능력을 가진
phrase
- 1
어떤 계산 모델, 시스템, 언어 등이 튜링 기계와 같은 범위의 계산을 수행할 수 있는 상태C2
having the same computational capability as a Turing machine, especially in being able to compute the same class of functions or simulate each other
Many formal models of computation are Turing equivalent, even though they look very different.
많은 형식적 계산 모델은 겉보기에는 매우 다르지만 튜링 기계와 동등한 계산 능력을 가진다.
The language was shown to be Turing equivalent to a standard Turing machine.
그 언어는 표준 튜링 기계와 동등한 계산 능력을 가진다는 것이 입증되었다.
뉘앙스 · 쓰임
‘Turing-complete’는 보통 어떤 시스템이 튜링 기계를 모의할 수 있을 만큼 강력하다는 점을 강조하고, ‘Turing equivalent’는 튜링 기계와 서로 같은 계산 능력을 가진다는 동등성에 더 초점이 있습니다. 실제 문맥에서는 두 표현이 가깝게 쓰이기도 하지만, 엄밀한 이론적 글에서는 구별될 수 있습니다.
전문 용어이므로 일반 독자에게는 설명을 덧붙이는 것이 좋습니다. 하이픈을 넣어 형용사처럼 ‘Turing-equivalent system’이라고 쓰는 경우가 많고, 명사 뒤에서는 ‘is Turing equivalent to a Turing machine’처럼 씁니다. ‘Turing’은 인명 Alan Turing에서 온 말이므로 대문자로 씁니다.
유의어 뉘앙스 비교
- Turing-complete
- 대체로 비슷하지만, ‘Turing-complete’는 튜링 기계를 모의할 수 있는 충분한 계산 능력을 강조하고, ‘Turing equivalent’는 튜링 기계와의 상호 동등성을 더 엄밀하게 나타냅니다.
- computationally universal
- 계산적으로 보편적이라는 더 설명적인 표현이며, 특정하게 튜링 기계를 기준으로 한 표현은 아닐 수 있습니다.
반의어
- finite-state
- 유한한 상태만 가지는 계산 모델을 가리키며, 일반적으로 튜링 기계만큼 강력하지 않습니다.
- sub-Turing
- 튜링 기계보다 계산 능력이 약한 모델이나 체계를 가리키는 이론적 표현입니다.
어원 · 암기 팁
[English]‘Turing’은 영국 수학자이자 컴퓨터 과학의 선구자인 Alan Turing의 이름에서 왔습니다. 튜링은 계산 가능성을 설명하기 위해 추상적 계산 장치인 ‘Turing machine’을 제안했고, 이후 어떤 시스템이 이와 같은 계산 능력을 가지는지를 설명하는 표현으로 ‘Turing equivalent’가 쓰이게 되었습니다.
💡 ‘Turing machine과 equivalent(동등한)’라고 나누어 기억하면, ‘튜링 기계와 계산 능력이 같은’이라는 뜻을 쉽게 떠올릴 수 있습니다.