튜링 완전 (Turing Complete)

튜링 완전은 어떤 계산 시스템이나 프로그래밍 언어가 튜링 기계를 흉내 낼 수 있어, 메모리와 시간이 충분하다면 계산 가능한 모든 알고리즘을 실행할 수 있다는 성질입니다. 이름은 1936년 계산의 추상 모델인 튜링 기계를 제시한 영국 수학자 앨런 튜링에게서 왔습니다. Python, JavaScript, C++ 같은 대부분의 범용 프로그래밍 언어는 튜링 완전이며, 블록체인에서는 이더리움 가상 머신(EVM)이 대표적인 예입니다.

무엇이 필요한가

실제로는 조건 분기, 반복(또는 재귀), 그리고 필요한 만큼 읽고 쓸 수 있는 메모리가 있으면 튜링 완전이 됩니다. 튜링 완전성은 무엇을 계산할 수 있는가에 대한 성질일 뿐, 얼마나 빠르거나 효율적인지와는 관계가 없습니다.

정지 문제

튜링 완전한 언어로 쓴 임의의 프로그램이 끝나는지, 무한히 도는지를 미리 판정하는 일반적인 알고리즘은 존재하지 않습니다(튜링의 정지 문제). 블록체인에서는 이것이 실질적인 문제입니다. 모든 노드가 같은 코드를 실행해야 하는데, 끝나지 않는 프로그램 하나가 네트워크 전체를 멈추게 할 수 있기 때문입니다.

이더리움: 가스로 제한된 튜링 완전

EVM 명령어는 반복과 분기를 지원해 언어 수준에서는 튜링 완전입니다. 대신 모든 연산에 가스 비용이 매겨지고 트랜잭션마다 가스 한도가 정해지므로, 어떤 실행도 가스를 다 쓰면 중단됩니다. 그래서 이더리움 황서는 EVM을 “준(quasi) 튜링 완전”이라고 표현합니다. 정지 여부를 미리 판정할 필요 없이, 실행 길이를 비용으로 제한하는 방식입니다.

비트코인 스크립트: 의도된 비완전성

비트코인 스크립트는 반복문과 임의 점프가 없어 일부러 튜링 완전하지 않게 설계되었습니다. 스크립트의 실행 길이가 그 크기로 제한되므로 검증 비용을 예측하기 쉽고 공격 표면이 작습니다. 이처럼 튜링 완전성은 블록체인마다 선택 사항이며, “스마트 계약 플랫폼이면 모두 튜링 완전”인 것은 아닙니다.

장점과 위험

• 표현력: 탈중앙화 거래소, 대출 프로토콜, 토큰 표준 등 임의의 논리를 스마트 계약으로 구현할 수 있습니다.
• 보안 위험: 표현력이 큰 만큼 코드의 동작을 모든 경우에 대해 검증하기 어렵고, 재진입(reentrancy) 같은 버그가 큰 손실로 이어진 사례가 있습니다. 형식 검증과 감사로 위험을 줄이지만 없애지는 못합니다.
• 자원 비용: 모든 노드가 연산을 반복하므로 복잡한 계약일수록 가스 비용이 커집니다.