튜링 완전성 (Turing completeness)
쉽게 풀면
어떤 프로그래밍 언어나 시스템이 '튜링 완전하다'는 것은 이론적으로 튜링 기계가 할 수 있는 어떤 계산도 그 언어로 표현할 수 있다는 뜻이다. 놀랍게도 스프레드시트 수식이나 게임 안의 특정 규칙, 심지어 카드 게임의 규칙처럼 계산을 위해 설계되지 않은 시스템도 조건문과 반복(또는 그와 동등한 것)을 표현할 수 있으면 튜링 완전해질 수 있다. 반대로 튜링 완전하다는 것은 정지 문제와 같은 결정 불가능성의 한계도 함께 가진다는 뜻이기도 하다.
왜 중요한가
어떤 시스템이 튜링 완전한지 아닌지는 그 시스템이 원리적으로 무엇을 표현할 수 있는지를 가르는 경계선이기 때문에, 새로운 프로그래밍 언어나 도메인 특화 언어를 설계할 때, 또는 회로·게임·스마트 컨트랙트 같은 비전통적 시스템의 표현력을 논할 때 자주 인용됩니다. 특히 표현력이 강할수록 정지 여부 같은 성질을 일반적으로 보장할 수 없다는 대가가 따르기 때문에, 보안이나 자원 제한이 중요한 시스템을 설계할 때는 의도적으로 튜링 완전성을 제한하는 선택을 하기도 합니다.
논문에서는 이렇게 쓰입니다
언어나 시스템의 표현력의 상한을 설명하거나, 그로 인한 결정 불가능성 문제를 지적할 때 사용된다.
하드웨어나 회로 설계처럼 계산을 목적으로 만들어지지 않은 시스템도 특정 조건에서 튜링 완전해질 수 있음을 논증하는 문장이다.
표현력을 일부러 제한해 안전성이나 종료 보장 같은 다른 성질을 얻는 설계 선택을 보여주는 예문이다.
조금 더 깊게 보면
어떤 시스템이 튜링 완전함을 증명하는 대표적인 방법은 이미 튜링 완전하다고 알려진 다른 모델(튜링 기계, 람다 계산법, 특정 규칙 기반 시스템 등)을 그 시스템 안에서 흉내 낼 수 있음을 보이는 것입니다. 이런 상호 시뮬레이션 가능성 논증을 흔히 환원(reduction)이라고 부릅니다. 실무에서는 조건 분기와 무한히 커질 수 있는 상태(또는 메모리)를 표현할 수 있는지가 튜링 완전성 여부를 가르는 핵심 조건으로 자주 언급됩니다.
주의할 점
튜링 완전성은 표현력의 상한을 의미할 뿐 실용성이나 효율성을 보장하지 않으며, 튜링 완전한 시스템은 정지 여부를 일반적으로 판별할 수 없다는 대가를 치른다.