프로그래밍 언어론
Turing Complete튜링 완전
튜링 완전(Turing Complete)은 어떤 계산 시스템이 튜링 머신(Turing Machine)과 동일한 계산 능력을 가질 때 사용하는 표현이다. 즉, 충분한 시간과 메모리가 주어진다면 임의의 알고리즘을 표현하고 실행할 수 있다는 의미다.
개념 배경
1936년 영국 수학자 앨런 튜링(Alan Turing)이 제안한 튜링 머신은 이론적인 계산 모델로, 모든 계산 가능한 문제를 해결할 수 있다.
어떤 언어나 시스템이 튜링 완전하다는 것은 다음을 지원한다는 뜻이다:
| 기능 | 설명 |
|---|---|
| 조건 분기 | if, while 등 조건에 따른 실행 |
| 반복 | 무한 루프 포함 임의 반복 |
| 임의 메모리 | 이론적으로 무한한 메모리 접근 |
| 함수/재귀 | 자기 참조 계산 |
일반 프로그래밍 언어 중 Python, Java, C++, Rust 등은 모두 튜링 완전하다.
블록체인에서의 중요성
Bitcoin vs Ethereum
| 항목 | Bitcoin | Ethereum |
|---|---|---|
| 스크립트 언어 | Script (비튜링 완전) | EVM 바이트코드 (튜링 완전) |
| 표현 가능 로직 | 단순 결제 조건 | 임의의 프로그램 |
| 스마트 컨트랙트 | 제한적 | 완전 지원 |
Bitcoin의 Script는 의도적으로 튜링 완전하지 않게 설계됐다. 단순 결제 처리에 충분하고, 무한 루프가 불가능해 실행 시간을 예측할 수 있어 보안 리스크를 줄인다. 반면 Ethereum의 EVM은 튜링 완전해서 스마트 컨트랙트로 DeFi, DAO, NFT 등 복잡한 로직을 구현할 수 있다.
할팅 문제 (Halting Problem)
튜링 완전 시스템의 한계: 어떤 프로그램이 무한 루프에 빠질지 미리 판단하는 것은 불가능하다(할팅 문제). 이더리움은 이를 Gas 시스템으로 해결한다. 계산량에 비례해 Gas를 소모하고, Gas가 고갈되면 실행이 중단된다. Gas는 무한 루프의 현실적 방어막 역할을 한다.
비튜링 완전 시스템의 장점
튜링 완전이 항상 유리한 것은 아니다. 비완전 시스템은:
- •실행 시간이 보장되어 DoS 공격에 강함
- •코드 분석·감사가 용이
- •Bitcoin Script처럼 목적이 명확한 경우 더 안전
실제 응용 사례
튜링 완전 블록체인이 가능하게 하는 것들:
| 분야 | 예시 |
|---|---|
| DeFi | 자동화된 대출·교환·이자 지급 로직 |
| DAO | 온체인 투표·거버넌스 실행 |
| NFT | 복잡한 민팅 조건, 로열티 자동 분배 |
| 게임 | 온체인 게임 로직, 아이템 시스템 |
관련 개념
- •Ethereum — 튜링 완전 스마트 컨트랙트 플랫폼
- •스마트 컨트랙트 — 튜링 완전 언어로 작성된 블록체인 프로그램
- •Solidity — 이더리움의 튜링 완전 스마트 컨트랙트 언어
- •EVM — 이더리움의 튜링 완전 가상 머신
- •가스 — 튜링 완전의 할팅 문제 해결책
참고문헌
- •Turing, A. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem
- •Buterin, V. (2014). Ethereum Whitepaper
