[Ethereum] 튜링이란?

이더리움을 공부하던 중 Turing comlete 라는 용어를 접하게 되었는데 과연 정확히 무엇을 의미하는지 같이 한번 알아보도록 하죠.

 

튜링 완전(turing completeness)는 어떤 프로그래밍 언어나 추상 기게가 튜링 기계와 동일한 계산 능력을 가진다는 의미인데, 이것은 튜링 기계로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 기계로 풀 수 있다는 의미를 가르키고 있습니다.

 

제한 없는 크기의 기억 장치를 갖는 기계를 만드는 것이 불가능하므로, 진정한 의미의 튜링 완전 기계는 아마도 물리적으로 불가능할 것입니다. 그러나, 제한 없이 기억의 장치의 크기를 늘려갈 수 있다고 가정할 수 있는 물리적 기계 혹은 프로그래밍 언어에 대해서는, 느슨하게 튜링 완전하다고 간주합니다. 이러한 시스템을 Universal Turing machine (UTM)이라고 하였습니다.

 

메모리에 데이터를 읽고 쓰는 동안 이더리움 가상머신이라는 상태 머신에서 저장된 프로그램을 실행할 수 있는 이더리움의 기능은 Turing-completet 시스템이므로 UMT이 됩니다. 이더리움은 한정 메모리의 한계를 감안할 때 모든 튜링 기계로 계산할 수 있는 알고리즘을 계산 할 수 있습니다.