[Mastering Ethereum] 이더리움 튜링 완전

[Mastering Ethereum] 이더리움 튜링 완전

튜링 완전(Turing Completeness)

어떤 프로그래밍 언어나 추상 기계가 튜링 기계와 동일한 계산 능력을 가진다 라는 의미. 조건문 혹은 메모리의 임의 위치 값을 변경할 수 있으면 튜링 완전이라고 한다. HTML이나 SQL과 같은 스크립트 언어들을 제외하고 대부분의 프로그램이 언어들은 튜링 완전하다고 볼 수 있다.

어떻게 만들어졌나?

1936년 기계의 일반 개념을 설명하기 위해 영국인 수학자 앨런 튜링이 사용함. 순차적 메모리(무한대의 종이테이프)에서 기호를 읽고 쓰는 방식으로 기호를 조작하는 상태 머신으로 구성된 컴퓨터의 수학적 모델을 만듬. 이 구성을 통해 튜링 머신은 모든 계산 문제를 해결할 수 있는 보편적 계산 가능성을 가지고 있으며, 정지 문제(튜링머신이 정지 되었는가 정지 되지 않았는가를 판단하는 것)가 해결되지 않는다 는 것을 증명했다. 이러한 시스템을 UTM(Universal Turing Machine)이라고 한다.

기능으로써 튜링 완전

튜링 완전은 아주 쉽게 달성할 수 있다. 튜링 완전은 개방형 액세스 환경에서 매우 위험하다. 왜냐하면 바로 정지 문제 때문이다. 예를 들어서 최신 프린터들은 튜링 완전해서 프린터가 작동 불능 상태가 될 때까지 인쇄 명령을 받을 수도 있다. 이러한 유연성은 블록체인에서는 매우 어려운 문제를 야기한다.

튜링 완전의 함축적 의미

- 튜링은 프로그램 종료 여부를 예측할 수 없는 증명을 했다. 즉, 프로그램을 실행하지 않고선 프로그램 경로를 예측할 수 없다는 것이다.

- 모든 참여 노드(클라이언트)는 모든 트랜잭션을 검증하고 그 트랜잭션이 호출하는 스마트 컨트랙트를 실행해야 한다. 하지만, 튜링이 증명한 것처럼 이더리움은 스마트 컨트랙트가 종료될지 혹은 실제로 스마트 컨트랙트를 실행하지 않고 얼마나 오랫동안 실행될지 예측할 수 없다.

이더리움은 '가스'로 자원을 제한

EVM이 스마트 컨트랙트를 실행하게 되면, 가스는 각 명령어를 일일이 계산한다. 각 명령어는 가스 단위로 미리 정해진 비용이 있다. 즉, 스마트 컨트랙트를 실행 시킬때, 트랜잭션은 스마트 컨트랙트를 실행하는 데 사용할 수 있는 가스의 최대 사용량을 가지고 있어야 한다.

(Ex 계산에 소비되는 가스의 총량이 트랜잭션에서의 가스 가용량을 초과한다면 EVM은 실행을 중지할 것이다.)

참고할 블로그: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId;=mage7th&logNo;=221561274756

from http://jihyuns-today.tistory.com/55 by ccl(A) rewrite - 2021-11-21 23:26:35