튜링 완전언어
튜링 완전성(Turing completeness)은 계산 이론에서 언어나 시스템이 튜링 머신과 동일한 계산 능력을 가지고 있음을 의미합니다. 다시 말해서, 언어나 시스템이 튜링 완전하다면 그것으로 모든 계산 가능한 문제를 풀 수 있다는 것입니다.
튜링 완전언어의 조건
-
기본적인 연산
덧셈, 뺄셈, 곱셈, 나눗셈 등의 기본 연산이 가능해야합니다. -
메모리
데이터를 저장하고 참조할 수 있는 무한한 메모리나 저장공간이 필요합니다. -
조건문과 반복문
특정 조건에 따라 코드를 실행하거나, 코드를 반복 실행하는 구조가 필요합니다.
튜링 완전 언어들
많은 프로그래밍 언어들, 우리가 아는 파이썬이나 자바 그리고 C++ 이나, 자바스크립트는 튜링 완전합니다.
튜링완전성 - 솔리디티
솔리디티는 이더리움 블록체인에서 스마트 컨트랙트를 작성하기 위한 프로그래밍 언어입니다. 스마트 컨트랙트는 블록체인 상에서 자동으로 실행되는 프로그램이며, 거래와 계약 조건을 코드로 기술할 수 있습니다.
솔리디티는 튜링 완전한 언어로 설계되었습니다. 이 말은 솔리디티를 사용해서 위에서 언급한 1. 기본적 연산, 2. 메모리 조작, 3. 조건 및 반복 구문 등의 게산 기능을 구현할 수 있다는 것을 의미합니다. 그러니 이론적으로는 솔리디티로 작성된 스마트 컨트랙트는 어떤 계산 가능한 문제도 해결할 수 있습니다.
그러나 튜링 완전성은 이더리움에서 몇가지 중요한 문제점을 발생시킵니다.
튜링완전성이 이더리움에서 발생시키는 문제점들
-
가스비 Gas fee
이더리움에서 모든 트랜잭션과 스마트 컨트랙트 실행에는가스라는 비용이 들어갑니다. 그러니까 복잡한 계산이나 긴 연산은 많은 가스를 필요로 하고, 여기서 효율적인 코드 작성은 많이 중요합니다. -
정지문제 Halting problem
어떤 프로그램이 정지할지 안할지 예측하는 것은 불가능합니다. 그렇기 때문에 스마트 컨트랙트의 실행이무한히 반복될 수있고, 이것은가스 소진으로 이어질 수 있습니다.
Appendix
튜링머신
튜링머신은 1936년에 앨런 튜링이라는 사람에 의해서 제안된 가상의 계산 모델입니다. 이 모델은 모든 계산 가능한 문제를 수학적으로 표현하고 연구하기 위해서 개발되었습니다. 튜링 머신은 모든 알려진 컴퓨팅 시스템의 계산 능력을 시뮬레이션할 수 있으며, 현대 컴퓨터의 이론적 기초를 제공했습니다.
튜링 머신의 주요 구성요소
-
무한한 길이의 테이프 Tape
각각의 셀에는 심볼이 기록될 수 있습니다. 이 테이프는 왼쪽과 오른쪽으로 무한히 확장될 수 있습니다. -
테이프헤드 Head
현재의 심볼을 읽거나 쓸 수 있으며, 왼쪽 또는 오른쪽의 셀로 이동할 수 있습니다. -
상태기계 Finite Control
다양한 상태들을 가지며, 현재 상태와 테이프 헤드에 의해 읽힌 심볼에 따라 동작을 결정합니다.
튜링머신의 작동
- 상태 기계는 현재 상태를 확인합니다.
- 테이프 헤드는 현재 위치의 심볼을 읽습니다.
- 상태 기계는 테이블(또는 전이함수)을 참조하여 다음 동작을 결정합니다. 이 동작은 심볼을 쓰고, 테이프 헤드를 움직이며, 상태를 변경하는 것으로 구성될 수 있습니다.
- 튜링 머신은 종료 상태에 도달할 때까지 위의 과정을 반복합니다.
튜링 머신은 이론적인 모델이어서 실제로 구현되지는 않았습니다. 그러나 오늘날 모든 컴퓨터는 튜링 머신의 능력을 모방하도록 설계되었으며, 어떤 문제가 튜링 머신으로 계산 가능한지를 결정하는 것은 그 문제가 현대의 컴퓨터로도 계산가능한지를 결정하는 것과 동일하다고 볼 수 있습니다.
