이전글보기

1. 블록체인이란?

• 1-1. 블록체인 기술 정의
• 1-2. 머클트리(merkle tree)란?

2. 채굴방식(마이닝) POW, POS, DPOS 란?
3. 스마트 컨트랙트란(Smart Contracts)?
4. 퍼블릭 블록체인, 프라이빗(컨소시움) 블록체인 비교
5. 튜링 완전(turing-complete)이란?

튜링 완전이란?

튜링 완전(turing complete) 이란 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력을 가진다는 의미이며 튜링 머신으로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 머신으로 풀 수 있다는 의미입니다.

튜링이란?

수학자 앨런 튜링이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계이며 오토마타의 일종이다. 튜링은 이 개념을 automatic에서 따온 a-machine이라고 불렀는데 튜링 사후에 창시자의 이름을 따 튜링 머신이라고 부르게 되었다.

라고 나무위키에서 정의되어 있습니다.

튜링 머신 장치

• 테이프(Tape) : 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있음

• 헤드(Head) : 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다. 또는 헤드는 고정되어 있고 테이프가 이동

• 상태 기록기(State register) : 현재 튜링 머신의 상태를 기록하고 있는 장치

  • 개시 상태(Start state) : 상태 기록기가 초기화된 상태를 의미
  • 종료 상태(Halt state) : 수행이 종료된 상태

• 행동표(Action table, transition table of instructions) : 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시

  • 기호를 지우거나 고쳐 씀
  • 헤드를 오른쪽, 왼쪽으로 한 칸 움직이거나 그 자리에 머뭄
  • 상태를 변경한다. 같은 상태에 머무를 수도 있음

튜링머신에 대해 복잡한 문서가 있는데 컴퓨터는 보편 튜링 머신 이론에 바탕을 두고 있습니다. 간단하게 컴퓨터 = 튜링머신 이라고 이해하는게 빠릅니다(약간의 차이가 존재). 따라서 튜링 머신은 컴퓨터를 흉내낼 수 있습니다. 컴퓨터의 작업을 이론적으로 모델링할 때 튜링 머신을 활용합니다.

물론 약간의 차이점이 있는데 튜링 머신은 아무 위치나 원할 때 접근할 수 없습니다. 이진탐색(binary search)와 같은 알고리즘의 시간복잡도는 임의 접근이 가능하다면 O(logN) 시간이 걸리지만 튜링 머신에서는 O(N)의 시간이 걸립니다.

현실의 모든 컴퓨터 또한 튜링 완전하지 않은데, 그 이유는 기억장치가 유한하기 때문입니다. '만일 기억장치가 무한하다면 이 컴퓨터는 튜링 완전하다'라고 생각할 수도 있는데 이것을 느슨한 튜링 완전성(Loose Turing Completeness) 이라고 합니다. 대부분의 컴퓨터는 느슨하게 튜링 완전합니다. 그렇기 때문에 어떤 컴퓨터가 할 수 있는 모든 일은 아주 충분한 시간과 메모리만 주어진다면 다른 어떤 간단한 컴퓨터로도 할 수 있습니다.

요약

• 튜링은 계산하는 기계를 만든 사람의 이름을 따옴
• 튜링완전하다는 것은 튜링머신과 동일한 계산능력을 지녔다는 의미
• 복잡하게 더 이해할 필요성을 못느낌