해시넷
"튜링완전"의 두 판 사이의 차이
| 1번째 줄: | 1번째 줄: | ||
| − | '''튜링완전'''(turing-complete)는 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력으로 문제를 풀 수 있다는 의미이다. '''튜링'''은 수학자 '''앨런 튜링'''이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계를 뜻한다.<ref>불곰, 〈[https://brownbears.tistory.com/369 튜링완전(turing-complete)이란?]〉, 《티스토리》, 2018-07-05</ref> | + | '''튜링완전'''(turing-complete)는 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력으로 문제를 풀 수 있다는 의미이다. '''튜링'''은 수학자 '''앨런 튜링'''이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계를 뜻한다.<ref name="불곰>불곰, 〈[https://brownbears.tistory.com/369 튜링완전(turing-complete)이란?]〉, 《티스토리》, 2018-07-05</ref> |
== 개요 == | == 개요 == | ||
| 15번째 줄: | 15번째 줄: | ||
* '''상태 기록기''' : 상태 기록기(State register)은 현재 튜링 머신의 상태를 기록하고 있는 장치이다. | * '''상태 기록기''' : 상태 기록기(State register)은 현재 튜링 머신의 상태를 기록하고 있는 장치이다. | ||
* '''행동표''' : 행동표(Action table, transition table of instructions)는 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다.<ref name="불곰></ref> | * '''행동표''' : 행동표(Action table, transition table of instructions)는 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다.<ref name="불곰></ref> | ||
| + | |||
| + | === 튜링완전언어 === | ||
| + | 튜링완전언어(Turing-Complete Language)는 튜링머신에 넣어야할 알고리즘을 만들 수 있는 언어이며 완전한 작동을 위해서 충족되어야 할 조건이 있다. 튜링완전언어는 프로세스를 충분히 분할할 수 있을 만큼 작은 단위를 사용할 수 있어야 하며 조건설정과 반복 명령어가 있어야 한다.<ref name="한승환"></ref> 일반적으로 많이 알려진 기계어나 어셈블이어의 경우, 충분히 작은 단위로 나뉘어있지만, 실용성이 낮다. C언어와 자바(Java)처럼 분할 정도나 실용성측면에서 충분하지 못한 언어들을 '''느슨한 튜링완전'''(Loose Turing Completeness)이라고 부른다.<ref name="디센터"></ref> | ||
{{각주}} | {{각주}} | ||
2019년 5월 24일 (금) 16:41 판
튜링완전(turing-complete)는 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력으로 문제를 풀 수 있다는 의미이다. 튜링은 수학자 앨런 튜링이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계를 뜻한다.[1]
개요
튜링완전은 암호학자인 엘런 튜링(Alan M.Turing)에 의해 1936년에 고안된 개념이다. 엘런 튜링은 기계의 일반적인 개념을 설명하기 위하여 고안한 가상의 기계로 튜링을 제시하였다. 앨런 튜링은 기계가 진짜 인간처럼 보일 수 있게 구현할 수 있다면 해당 기계는 지능적으로 인공지능에 대한 테스트를 통과하였다고 보았다.이더리움을 가능하게 만든 핵심 개념인 튜링완전은 튜링 테스트를 통과한 경우에만 확보된다. 튜링완전은 무한한 저장공간을 바탕으로 현존하는 모든 문제를 풀 수 있는 기계인 튜링머신(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]
각주
- ↑ 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
참고자료
- 불곰, 〈튜링완전(turing-complete)이란?〉, 《티스토리》, 2018-07-05
- 한승환, 〈이더리움 개론 + 튜링완전 (Ethereum Introduction)〉, 《개인 블로그》, 2015-06-04
- 이화여대 융합보안연구실, 〈(디센터 아카데미(3부)) ⑧블록체인에서 튜링 완전성이 가지는 의미〉, 《디센터》, 2019-01-15
같이 보기
