Turing completeness의 형용사는 Turing complete이다.
튜링 완전 (Turing completeness)의 의미는 어떤 컴퓨터가 튜링 머신(Turing Machine)이 할 수 있는 일을 내부 동작은 다르더라도 결과가 똑같은 일을 할 수 있다면 그 컴퓨터를 Turing complete이라고 부른다.
튜링 머신이란 쉽게 생각하면 현재의 일반적인 컴퓨터를 생각하면 된다. 그렇다면 모든 컴퓨터는 Turing complete하다는 말인데 그것이 무슨 의미일까? 현재의 컴퓨터는 튜링 머신에서부터 발전해 왔기 때문에 거의 모든 컴퓨터는 튜링 머신과 비슷하게 동작하기 때문에 지금에서는 너무나 당연한 말이지만 과거에는 그렇지 않았다. 그리고, 만약 새로운 CPU를 설계한다면 그 CPU를 Turing complete하게 설계해야 한다. 그렇지 않으면 그 CPU는 다른 컴퓨터에서는 할수 있는 특정 작업을 할 수 없는 문제가 생길 수 있다.
그리고, Turing complete은 프로그램 언어에서도 쓰인다. 일반적인 C, BASIC은 모든 작업을 할 수 있는 Turing complete 언어이다. 하지만, 특정한 목적으로 사용되는 스크립트 언어에서는 Turing complete 하지 않는 언어가 있다. 그러한 언어를 쓸때는 특정 목적으로는 사용할 수 있지만 다른 작업을 하는 프로그램을 작성하려고 할때 어려움이 있을 수 있다.
컴퓨터가 Turing complete 하기 위해서는 Conditional Branch 명령과 모든 메모리 데이터를 변경할 수 있으면 된다. 이 2가지가 된다면 사칙연산, 게임, 동영상 재생, 통계분석 등 현재 일반적인 컴퓨터가 할수 있는 모든 것을 이 2가지를 조합하여 할수가 있다.
즉, 컴퓨터 자체가 사칙연산을 지원하지 않아도 위의 2가지 명령의 조합으로 사칙연산을 구현할 수 있고 현재 우리가 일반적으로 아는 모든 알고리즘을 위의 2가지 명령의 조합으로 구현할 수 있다.
Turing complete을 만족하는 가장 간단한 컴퓨터를 직접만들 수도 있다. 전자공학과 학부에서 배우는 어떤 컴퓨터 구조 책에서는 AND, OR 등의 로직 게이트로 CPU를 만드는 것에 관해 설명하고 있다.
'컴퓨터' 카테고리의 다른 글
SATA와 NVMe의 차이 (0) | 2020.12.05 |
---|---|
삼각함수 테일러 시리즈 (0) | 2020.12.05 |
뉴턴-랩슨법 (0) | 2020.11.08 |
[C] sqrt() 함수 구현 (0) | 2020.11.08 |
위키 뜻 (0) | 2020.11.01 |
댓글