위키원
"튜링완전"의 두 판 사이의 차이
(→개요) |
|||
| 3번째 줄: | 3번째 줄: | ||
== 개요 == | == 개요 == | ||
| − | + | 튜링완전은 암호학자인 [[엘런 튜링]](Alan M.Turing)에 의해 1936년에 고안된 개념이다. 그는 1936년에 "결정 문제에 적용한 연산 가능한 숫자에 관하여"라는 논문을 발표했다. 여기서 그는 인간의 도움 없이도 일련의 지침들을 수행할 수 있는 가설적 [[컴퓨터]]를 고안하고, 기계의 일반적인 개념을 설명하기 위하여 고안한 가상의 기계로 '''튜링'''이란 머신을 제시하였다. [[앨런 튜링]]은 기계가 진짜 인간처럼 보이도록 구현할 수 있다면 해당 기계는 지능적으로 인공지능에 대한 테스트를 통과하였다고 보았다. [[이더리움]]을 가능하게 만든 핵심 개념인 튜링완전은 튜링 테스트를 통과한 경우에만 확보된다. 컴퓨터로 실험자 2명이 서로 대화할 때 누가 사람인지 구분할 수 없다면 컴퓨터는 인공지능을 갖춘 것이다. 이것을 튜링 완전성이라고 한다. 튜링완전은 무한한 저장공간을 바탕으로 현존하는 모든 문제를 풀 수 있는 기계인 '''[[튜링머신]]'''(Turing Machine)을 만든다. 이러한 튜링머신은 '''튜링완전언어'''(Turing Complete Language)를 바탕으로 [[알고리즘]]이 구현된다. 튜링완전은 이러한 [[튜링완전언어]]를 통해서 확보된다.<ref name="디센터">이화여대 융합보안연구실, 〈[https://decenter.sedaily.com/NewsView/1VE1PVFSZQ/GZ05 (디센터 아카데미(3부)) ⑧[[블록체인]]에서 튜링 완전성이 가지는 의미]〉, 《디센터》, 2019-01-15</ref> | |
| − | |||
| − | |||
| − | |||
| − | 튜링완전은 무한한 저장공간을 바탕으로 현존하는 모든 문제를 풀 수 있는 기계인 '''[[튜링머신]]'''(Turing Machine)을 만든다. 이러한 튜링머신은 '''튜링완전언어'''(Turing Complete Language)를 바탕으로 [[알고리즘]]이 구현된다. 튜링완전은 이러한 [[튜링완전언어]]를 통해서 확보된다.<ref name="디센터">이화여대 융합보안연구실, 〈[https://decenter.sedaily.com/NewsView/1VE1PVFSZQ/GZ05 (디센터 아카데미(3부)) ⑧[[블록체인]]에서 튜링 완전성이 가지는 의미]〉, 《디센터》, 2019-01-15</ref> | ||
== 특징 == | == 특징 == | ||
2019년 8월 2일 (금) 11:53 판
튜링완전(Turing-Complete)는 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력으로 문제를 풀 수 있다는 의미이다. 튜링은 수학자 앨런 튜링(Alan Turing)이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계를 뜻한다.[1] 앨런튜링 사후에 이름을 떠서 튜링 머신이라고 불리우게 되었다.
개요
튜링완전은 암호학자인 엘런 튜링(Alan M.Turing)에 의해 1936년에 고안된 개념이다. 그는 1936년에 "결정 문제에 적용한 연산 가능한 숫자에 관하여"라는 논문을 발표했다. 여기서 그는 인간의 도움 없이도 일련의 지침들을 수행할 수 있는 가설적 컴퓨터를 고안하고, 기계의 일반적인 개념을 설명하기 위하여 고안한 가상의 기계로 튜링이란 머신을 제시하였다. 앨런 튜링은 기계가 진짜 인간처럼 보이도록 구현할 수 있다면 해당 기계는 지능적으로 인공지능에 대한 테스트를 통과하였다고 보았다. 이더리움을 가능하게 만든 핵심 개념인 튜링완전은 튜링 테스트를 통과한 경우에만 확보된다. 컴퓨터로 실험자 2명이 서로 대화할 때 누가 사람인지 구분할 수 없다면 컴퓨터는 인공지능을 갖춘 것이다. 이것을 튜링 완전성이라고 한다. 튜링완전은 무한한 저장공간을 바탕으로 현존하는 모든 문제를 풀 수 있는 기계인 튜링머신(Turing Machine)을 만든다. 이러한 튜링머신은 튜링완전언어(Turing Complete Language)를 바탕으로 알고리즘이 구현된다. 튜링완전은 이러한 튜링완전언어를 통해서 확보된다.[2]
특징
튜링머신
튜링머신(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
같이 보기
