튜링 완전성
용어요약Turing Complete
충분한 시간과 메모리가 주어지면 이론상 계산 가능한 모든 문제를 처리할 수 있는 계산 체계의 성질을 뜻하며, 블록체인에서는 스마트 컨트랙트의 표현력을 가늠하는 기준으로 쓰인다.
1.개요
튜링 완전성(Turing Complete)은 어떤 계산 체계가 앨런 튜링이 고안한 이론적 계산 모델인 튜링 머신과 동등한 계산 능력을 지녔음을 뜻하는 개념이다. 구체적으로는 조건 분기(if), 반복(loop), 임의의 메모리 읽기·쓰기를 표현할 수 있어, 시간과 저장 공간이 충분하다면 이론상 계산 가능한 모든 문제를 풀 수 있는 상태를 가리킨다. 대부분의 범용 프로그래밍 언어(파이썬, 자바, C 등)는 튜링 완전하다.
블록체인 분야에서 이 용어가 자주 쓰이는 이유는, 블록체인이 지원하는 프로그래밍 언어의 표현력에 따라 그 위에서 구현할 수 있는 애플리케이션의 범위가 결정되기 때문이다. 비트코인의 스크립트 언어는 무한 반복을 허용하지 않는 등 의도적으로 튜링 완전하지 않게 설계되어, 단순한 조건부 송금 이상의 복잡한 로직을 담기 어렵다. 반면 이더리움은 튜링 완전한 가상머신(EVM)과 스마트 컨트랙트 언어를 도입해, 임의의 프로그램을 블록체인 위에서 실행할 수 있도록 했다.
2.상세
튜링 완전한 시스템에는 근본적인 한계가 따른다. 어떤 프로그램이 언젠가 멈출지, 아니면 무한히 실행될지를 미리 판정하는 일반적 방법이 존재하지 않는다는 '정지 문제(halting problem)'가 그것이다. 블록체인은 모든 노드가 동일한 코드를 반복 실행해 상태를 검증하므로, 무한 루프에 빠진 컨트랙트 하나가 네트워크 전체를 멈추게 할 수 있다.
이더리움은 이 문제를 '가스(gas)'라는 수수료 메커니즘으로 해결한다. 컨트랙트가 실행하는 모든 연산에는 일정한 가스 비용이 매겨지고, 거래를 보낸 사용자가 미리 지불한 가스가 소진되면 실행이 강제로 중단된다. 즉 언어 자체는 튜링 완전하되, 자원 한도를 두어 실질적으로는 유한한 시간 안에 실행이 끝나도록 강제하는 방식이다. 이 때문에 이더리움 계열 플랫폼을 '준(quasi) 튜링 완전' 또는 '가스로 제한된 튜링 완전'이라 부르기도 한다.
3.예시
튜링 완전한 스마트 컨트랙트가 있었기에 오늘날의 복잡한 온체인 애플리케이션이 가능해졌다. 대표적으로 탈중앙화 거래소는 사용자의 예치·교환·수수료 정산 로직을 코드로 자동 실행하는데, 이는 단순 송금만 지원하는 언어로는 구현하기 어렵다. 마찬가지로 트랜잭션 처리를 메인 체인 밖에서 수행하는 레이어 2 솔루션들도 정산·검증 로직을 스마트 컨트랙트로 표현하기 위해 튜링 완전한 실행 환경에 의존한다.
반대로 비트코인은 튜링 완전성을 포기함으로써 스크립트의 실행 결과를 예측하기 쉽게 만들고 공격 표면을 줄이는 쪽을 택했다. 이는 튜링 완전성이 무조건 우월한 성질이 아니라, 표현력과 안전성·예측 가능성 사이의 설계상 절충임을 보여준다.
토큰포스트 위키, “튜링 완전성”, 2026-07-28 수정, https://wiki.tokenpost.kr/w/turing-completeAccept: text/markdown 로 요청해도 같은 결과문단 3개 · 연표 0건 · 각주 0개