Turing complete
숙어C2충분한 시간과 메모리가 있으면 어떤 계산도 표현하거나 수행할 수 있는
phrase
- 1
어떤 언어, 기계, 시스템, 규칙 집합이 충분한 시간과 메모리를 전제로 튜링 기계가 수행할 수 있는 모든 계산을 수행하거나 표현할 수 있는 상태C2
describes a language, machine, system, or set of rules that can, given sufficient time and memory, perform or express any computation that a Turing machine can perform
Most general-purpose programming languages, such as Python and JavaScript, are Turing complete.
파이썬과 자바스크립트 같은 대부분의 범용 프로그래밍 언어는 튜링 완전하다.
Surprisingly, the rules of the game can be arranged in a way that makes it Turing complete.
놀랍게도 그 게임의 규칙은 튜링 완전해지도록 배열될 수 있다.
뉘앙스 · 쓰임
‘powerful’이나 ‘flexible’은 일반적으로 강력하거나 유연하다는 뜻이지만, ‘Turing complete’는 계산 이론상 모든 알고리즘을 표현할 수 있다는 더 엄밀한 의미입니다. ‘computationally universal’은 거의 같은 뜻의 더 학술적인 표현이고, ‘general-purpose’는 실용적 범용성을 강조하지만 이론적 완전성을 반드시 뜻하지는 않습니다.
전문 용어이므로 일반 대화에서는 상대가 컴퓨터 과학 배경이 없으면 설명이 필요할 수 있습니다. 하이픈을 넣어 ‘Turing-complete’로 형용사처럼 명사 앞에 쓰는 경우가 많습니다. ‘Turing’은 사람 이름에서 온 말이므로 항상 대문자로 쓰는 것이 표준입니다.
유의어 뉘앙스 비교
- computationally universal
- 거의 같은 뜻이지만 더 학술적이고 계산 이론의 맥락이 강합니다.
- universal
- 문맥상 ‘universal computation’을 뜻할 때만 비슷하며, 단독으로는 의미가 모호할 수 있습니다.
- capable of universal computation
- 뜻을 풀어 쓴 표현으로, 전문 용어보다 설명적입니다.
반의어
- not Turing complete
- 튜링 완전하지 않다는 직접적인 반대 표현입니다.
- finite-state
- 유한한 상태만 가지는 시스템을 가리키며, 일반적으로 튜링 완전한 계산 능력보다 제한적입니다.
- regular
- 형식 언어 이론에서 정규 언어 수준의 제한된 계산 능력을 말할 때 쓰이며, 맥락 의존적입니다.
어원 · 암기 팁
[English]영국 수학자이자 컴퓨터 과학의 선구자인 Alan Turing의 이름에서 온 표현입니다. Turing이 제시한 추상 계산 모델인 ‘Turing machine’이 계산 가능성의 기준으로 쓰이면서, 그와 동등한 계산 능력을 가진 시스템을 ‘Turing complete’라고 부르게 되었습니다.
💡 ‘Turing’은 사람 이름, ‘complete’는 ‘완전한’이라는 뜻입니다. 즉 ‘튜링 기계만큼 계산 능력이 완전하다’고 기억하면 됩니다.