위키원
튜링완전
튜링완전(Turing-Complete)는 어떤 프로그래밍 언어나 추상 머신이 튜링머신과 동일한 계산 능력으로 문제를 풀 수 있다는 의미이다. 이것은 튜링 머신으로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 머신으로 풀 수 있다는 것이다. 튜링은 수학자 앨런 튜링(Alan Turing)이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계를 뜻한다.[1] 앨런튜링 사후에 이름을 떠서 튜링 머신이라고 불리우게 되었다.
개요
튜링완전은 수학자이자 암호학자인 엘런 튜링(Alan M.Turing)에 의해 1936년에 고안된 개념이다. 그는 1936년에 "결정 문제에 적용한 연산 가능한 숫자에 관하여"라는 논문을 발표했다. 여기서 그는 인간의 도움 없이도 일련의 지침들을 수행할 수 있는 가설적 컴퓨터를 고안하고, 기계의 일반적인 개념을 설명하기 위하여 고안한 가상의 기계로 튜링이란 머신을 제시하였다. 튜링완전은 무한한 저장공간을 바탕으로 현존하는 모든 문제를 풀 수 있는 기계인 튜링머신(Turing Machine)을 만든다. 이러한 튜링머신은 튜링완전언어(Turing Complete Language)를 바탕으로 알고리즘이 구현된다. 튜링완전은 이러한 튜링완전언어를 통해서 확보된다.[2]
주요 인물
- 엘런 튜링(Alan M.Turing):1911년, 아버지가 인도의 공무원으로 일하는 영국의 중산층 가정에서 태어났다. 그는 어린시절에 모범생은 아니였으나 수학과 과학만큼은 독자적인 철학을 정비할 정도로 뛰어났다. 케임브리지 킹스칼리지에서 '수리논리학'을 전공,1936년에는 불과 25세의 나이로 '계산 가능한 수와 결정문제의 응용에 대하여'라는 논문을 통해, '컴퓨터의 논리적 모형'을 제시하기에 이른다. 이후 미국 프린스턴 대학으로 옮겨 당대 최고의 수학자 폰 노이만을 지도교수로 박사 학위를 받은 그는, 2차 대전이 발발하자 함께 연구하자는 노이만의 제안을 거절하고 영국으로 귀국하였다.
- 애니악(eniac)이라는 1946년에 17000여개 이상의 진공관을 연결하여 만든 거대 계산기가 세계 최초의 컴퓨터라는 건 거짓말이다. 2년 전인 1944년에 난공불락으로 악명 높았던 독일의 견고한 암호, 에니그마(Enigma)를 해독하고자 영국의 일급 과학자들이 런던 근교의 블레츨리 파크에 모여 콜로서스(Colossus)라는 계산기를 영국에서 비밀리에 완성하였다. 1975년이 되어서야 비로소 공개되었다. 독일의 암호를 훤히 꿰뚫고 있었던 연합국은 승리의 교두보가 되었던 '노르망디 상륙작전'을 성공적으로 이끌 수 있었다. 슬픔, 행복, 심지어 살고자 하는 욕망까지 느끼는 기계가 과연 존재할 수 있을까? 라는 의문을 느끼고 인간의 지능과 감성을 가진 기계, 즉 '인공지능'(AI)이라는 개념은 1950년 앨런 튜링에 의해 처음 도입되었다.
특징
튜링머신
튜링머신(Turing Machine)은 추상적인 수학 개념상의 기계이다. 알고리즘 구현 언어인 튜링완전언어로 구현되며 무한한 저장공간만 있다면 이 세상의 모든 문제를 풀 수 있는 기계를 만드는 것이 가능한데, 그것을 튜링기계라고 한다.
튜링완전언어 + 무한한 저장공간 = 모든 계산 가능한 문제를 계산해내는 기계 = 튜링기계(인간의 뇌) [3]
튜링머신 장치
- 테이프 : 테이프(Tape)는 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프이다. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있다.
- 헤드 : 헤드(Head)는 종이 테이프의 특정 한 셀을 읽을 수 있고 이동이 가능하다.
- 상태 기록기 : 상태 기록기(State register)은 현재 튜링 머신의 상태를 기록하고 있는 장치이다.
- 행동표 : 행동표(Action table, transition table of instructions)는 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다.[1]
튜링완전언어
튜링완전언어(Turing-Complete Language)는 튜링머신에 넣어야할 알고리즘을 만들 수 있는 언어이며 완전한 작동을 위해서 충족되어야 할 조건이 있다. 튜링완전언어는 프로세스를 충분히 분할할 수 있을 만큼 작은 단위를 사용할 수 있어야 하며 조건설정과 반복 명령어가 있어야 한다.[3] 일반적으로 많이 알려진 기계어나 어셈블리어의 경우, 충분히 작은 단위로 나뉘어있지만, 실용성이 낮다. 이처럼 C언어와 자바(Java)처럼 분할 정도나 실용성측면에서 충분하지 못한 언어들을 느슨한 튜링완전(Loose Turing Completeness)이라고 부른다.[2]
루프
루프는 튜링완전언어의 특성에 따른 필수불가결한 특징으로 반복해서 돌아가는 것을 의미한다. 튜링완전이라는 특성은 어떠한 프로그램 혹은 애플리케이션도 만들어 낼 수 있음을 나타낸다. 이에 따라 튜링머신은 문제가 완전히 풀릴 때까지 반복하고 돌아간다. 루프 기능은 튜링머신의 이론에서 유용하고 반드시 필요한 부분이다. 하지만 이 특징은 득과실을 함께 포함하고 있다. 루프는 시간 제한이 없다. 무한 순환을 하여 그로 인해 튜링완전언어는 어떤 문제가 발생하여도 이에 대한 의도와 상관없이 끝까지 해결하기 위해 같은 작업을 반복한다. 결국 누군가 악의적으로 이러한 코드를 대입하여 루프기능을 악용한다면 이는 결국 메인 네트워크에 과부하를 불러일으키고, 더 나아가선 마비를 발생시키게 된다.[4]
수수료
이더리움은 루프로 인해 문제가 발생하는 상황을 피하고자 각 컴퓨터 코드 작업마다 수수료인 가스(gas)를 부과하는 시스템을 도입했다. 컴퓨터 코드가 실행될 때마다 수수료를 지불해야 한다면 개인의 악의적인 의도의 코드를 방지할 수 있다. 이뿐만 아니라 수수료인 가스는 노동의 보상으로써 작용하고 있다. 데이터를 옮기기 위해서는 채굴자들의 연산 작업이 필요한데, 이들이 한 계산에 대한 보상으로 이더리움 가스를 제공한다. 즉, 채굴자들은 채굴을 통해 채굴 보상과 연산 작업 보상을 함께 받게 된다.
각주
- ↑ 1.0 1.1 불곰, 〈튜링완전(turing-complete)이란?〉, 《티스토리》, 2018-07-05
- ↑ 2.0 2.1 이화여대 융합보안연구실, 〈(디센터 아카데미(3부)) ⑧블록체인에서 튜링 완전성이 가지는 의미〉, 《디센터》, 2019-01-15
- ↑ 3.0 3.1 한승환, 〈이더리움 개론 + 튜링완전 (Ethereum Introduction)〉, 《개인 블로그》, 2015-06-04
- ↑ jumsun, 〈[ETH 이더리움(Ethereum)에 대한 소소한 이야기 1. 튜링완전(Turing-Complete)언어]〉, 《스팀잇》, 2018-01-15
참고자료
- 불곰, 〈튜링완전(turing-complete)이란?〉, 《티스토리》, 2018-07-05
- 한승환, 〈이더리움 개론 + 튜링완전 (Ethereum Introduction)〉, 《개인 블로그》, 2015-06-04
- 이화여대 융합보안연구실, 〈(디센터 아카데미(3부)) ⑧블록체인에서 튜링 완전성이 가지는 의미〉, 《디센터》, 2019-01-15
- jumsun, 〈[ETH 이더리움(Ethereum)에 대한 소소한 이야기 1. 튜링완전(Turing-Complete)언어]〉, 《스팀잇》, 2018-01-15
같이 보기
