튜링 완전

3. 이론

계산 이론에서는 계산 시스템(예: 추상 기계 또는 프로그래밍 언어)의 계산 능력을 설명하기 위해 여러 가지 밀접하게 관련된 용어가 사용된다.

;튜링 완전성

: 튜링-계산 가능 함수를 모두 계산할 수 있는 계산 시스템을 튜링 완전(또는 튜링 강력)이라고 한다. 또는 이러한 시스템은 범용 튜링 기계를 시뮬레이션할 수 있는 시스템이다.

;튜링 동등성

: 튜링 완전 시스템은 그것이 계산할 수 있는 모든 함수가 튜링 계산 가능한 경우 튜링 동등하다고 한다. 즉, 튜링 기계와 정확히 같은 함수 클래스를 계산한다. 또는 튜링 동등 시스템은 범용 튜링 기계를 시뮬레이션하고, 범용 튜링 기계에 의해 시뮬레이션될 수 있는 시스템이다. (알려진 모든 물리적으로 구현 가능한 튜링 완전 시스템은 튜링 동등하며, 이는 처치-튜링 명제에 대한 지지를 더한다.^[9])

;(계산) 보편성

: 시스템의 클래스에 대해 시스템이 그 클래스의 시스템으로 계산 가능한 모든 함수를 계산할 수 있거나(또는 그러한 각 시스템을 시뮬레이션할 수 있는 경우) 그 시스템을 보편적이라고 한다. 일반적으로 '보편성'이라는 용어는 암묵적으로 튜링 완전 시스템 클래스와 관련하여 사용된다. "약하게 보편적인"이라는 용어는 때때로 (예: 셀룰라 오토마타) 표준 튜링 기계의 정의를 수정하여 무한히 많은 1을 포함하는 입력 스트림을 포함하도록 함으로써 보편성을 달성하는 시스템을 구분하는 데 사용된다.

튜링 완전성은 모든 실제 세계의 컴퓨팅 장치 설계를 튜링 기계가 시뮬레이션할 수 있다는 점에서 중요하다. 처치-튜링 명제는 이것이 수학의 법칙이며, 튜링 기계는 원칙적으로 다른 모든 프로그래밍 가능한 컴퓨터가 할 수 있는 모든 계산을 수행할 수 있다고 명시한다. 이것은 프로그램을 작성하는 데 필요한 노력이나 기계가 계산을 수행하는 데 걸리는 시간, 또는 계산과 관련이 없는 기계의 기능에 대해서는 아무것도 말하지 않는다.

찰스 배비지의 해석기관(1830년대)은 설계 당시 제작되었다면 최초의 튜링 완전 기계가 되었을 것이다. 배비지는 이 기계가 원시적인 논리적 추론을 포함한 엄청난 계산 능력을 가지고 있다는 것을 알았지만, 다른 어떤 기계도 이보다 더 나은 작업을 할 수 없다는 것을 알지 못했다. 1830년대부터 1940년대까지 가산기와 곱셈기와 같은 기계식 계산기가 제작 및 개선되었지만, 조건부 분기를 수행할 수 없었으므로 튜링 완전하지 않았다.

19세기 후반, 레오폴트 크로네커는 계산 가능성에 대한 개념을 공식화하여 원시 재귀 함수를 정의했다. 이러한 함수는 암기 계산으로 계산할 수 있지만, 이들을 계산하는 명령어가 무한 루프를 허용하지 않기 때문에 범용 컴퓨터를 만들기에 충분하지 않다. 20세기 초, 다비드 힐베르트는 기계로 수행할 수 있는 정확한 공리와 정확한 논리적 연역 규칙을 사용하여 모든 수학을 공리화하는 프로그램을 주도했다. 곧 소수의 연역 규칙만으로도 임의의 공리 집합의 결과를 생성하기에 충분하다는 것이 분명해졌다. 이 규칙들은 쿠르트 괴델이 1930년에 모든 정리를 생성하기에 충분하다는 것을 증명했다.

계산의 실제 개념은 그 직후 괴델의 불완전성 정리를 시작으로 분리되었다. 이 정리는 공리계가 자신의 정리를 연역하는 계산에 대해 추론할 때 제한적임을 보여주었다. 처치와 튜링은 독립적으로 힐베르트의 Entscheidungsproblem^de(결정 문제)가 풀 수 없다는 것을 증명하여 불완전성 정리의 계산적 핵심을 밝혔다. 이 작업은 일반 재귀 함수에 대한 괴델의 작업과 함께, 함께 놓으면 어떤 계산이라도 생성할 수 있는 단순한 명령어 집합이 있음을 확립했다. 괴델의 작업은 계산의 개념이 본질적으로 독특하다는 것을 보여주었다.

계산이론은 계산 모델을 사용하여 문제를 분석하고 그 문제가 계산 가능한지, 그리고 어떤 상황에서 계산 가능한지를 판단한다. 계산이론의 첫 번째 결과는 임의로 긴 시간 동안 (튜링 완전) 시스템이 무엇을 할지 예측하는 것이 불가능한 문제가 존재한다는 것이다.

대표적인 예시는 정지 문제이다. 튜링 완전 언어로 작성된 프로그램과 그 프로그램에 입력될 데이터를 입력으로 받아, 해당 프로그램이 입력 데이터를 처리하는 과정에서 결국 종료될지 아니면 무한히 계속될지를 판단하는 알고리즘을 만드는 것이다. 어떤 입력에 대해서는 이 작업을 수행하는 알고리즘을 만드는 것은 간단하지만, 일반적인 경우에는 불가능하다. 프로그램의 최종 출력의 어떤 특징에 대해서도 그 특징이 성립할지 여부를 판단하는 것은 불가능하다.

이러한 불가능성은 실제 세계의 컴퓨터 프로그램을 분석할 때 문제를 야기한다. 예를 들어, 프로그래머가 무한 루프를 작성하지 못하도록 완전히 보호하거나, 사용자가 무한 루프를 발생시키는 입력을 제공하지 못하도록 보호하는 도구를 작성할 수 없다.

대신 프로그램이 고정된 시간 동안만 실행되도록 제한(타임아웃)하거나, 제어 흐름 명령어의 기능을 제한할 수 있다(예: 기존 배열의 항목을 반복하는 루프만 제공). 그러나 또 다른 정리는 튜링 완전 언어로 풀 수 있지만 유한 반복 기능만 있는 언어(즉, 모든 프로그램이 결국 종료됨을 보장하는 언어)로는 풀 수 없는 문제가 존재한다는 것을 보여준다. 따라서 이러한 언어는 튜링 완전하지 않다. 예를 들어, 프로그램이 완료되고 종료됨이 보장되는 언어는 그 언어의 모든 계산 가능 함수에 대해 칸토어의 대각선 논법에 의해 생성되는 계산 가능 함수를 계산할 수 없다.

무한한 데이터 테이프에 접근할 수 있는 컴퓨터는 튜링 머신보다 더 강력할 수 있다. 예를 들어, 테이프에는 정지 문제 또는 다른 튜링적으로 결정 불가능한 문제의 해결책이 포함될 수 있다. 이러한 무한한 데이터 테이프를 튜링 오라클이라고 한다. 무작위 데이터를 가진 튜링 오라클조차도 계산 가능하지 않다(확률 1로). 계산은 가산 가능한 수만큼 있지만 오라클은 비가산 가능하기 때문이다. 따라서 무작위 튜링 오라클을 가진 컴퓨터는 튜링 머신이 할 수 없는 것을 계산할 수 있다.

튜링 기계 이외에도 튜링 완전한 계산 모델로는 람다 대수, μ 재귀 함수, 마르코프 알고리즘 등이 있다. 람다 대수가 튜링 완전하다는 것을 증명하는 데 중요한 점은, Y 조합자에 의해 람다 대수 내에서 재귀가 가능하고, 이것이 루프와 동등한 능력을 가진다는 것이다.

튜링 완전성에 관한 중요한 주제로는 처치-튜링 명제가 있다.

스티븐 울프럼은 이러한 문제를 오랫동안 연구해 온 것으로 알려져 있는데, 가장 단순하면서도 튜링 완전할 것으로 예상되는 계산 모델로 2상태 3기호 튜링 기계인 "2, 3 튜링 기계"에 주목하여, 2007년 그 보편성의 증명에 25000USD의 상금을 걸었다. 문제 제기 후 47일 후, 버밍엄 대학교 컴퓨터 과학부 학생이었던 알렉스 스미스가 긍정적 증명을 제출하여 상금이 확정되었다.^[38]

4. 성질

계산 이론에서 튜링-계산 가능 함수를 모두 계산할 수 있는 계산 시스템을 튜링 완전(또는 튜링 강력)이라고 한다. 또는 이러한 시스템은 범용 튜링 기계를 시뮬레이션할 수 있는 시스템이다.

튜링 완전 시스템은 그것이 계산할 수 있는 모든 함수가 튜링 계산 가능한 경우 튜링 동등하다고 한다. 즉, 튜링 기계와 정확히 같은 함수 클래스를 계산한다. 또는 튜링 동등 시스템은 범용 튜링 기계를 시뮬레이션하고, 범용 튜링 기계에 의해 시뮬레이션될 수 있는 시스템이다. (알려진 모든 물리적으로 구현 가능한 튜링 완전 시스템은 튜링 동등하며, 이는 처치-튜링 명제에 대한 지지를 더한다.)

시스템의 클래스에 대해 시스템이 그 클래스의 시스템으로 계산 가능한 모든 함수를 계산할 수 있거나(또는 그러한 각 시스템을 시뮬레이션할 수 있는 경우) 그 시스템을 보편적이라고 한다. 일반적으로 '보편성'이라는 용어는 암묵적으로 튜링 완전 시스템 클래스와 관련하여 사용된다. "약하게 보편적인"이라는 용어는 때때로 (예: 셀룰라 오토마타) 표준 튜링 기계의 정의를 수정하여 무한히 많은 1을 포함하는 입력 스트림을 포함하도록 함으로써 보편성을 달성하는 시스템을 구분하는 데 사용된다.

튜링 기계의 중요한 특성으로 정지 문제가 있다.

먼저, 튜링 기계는 반드시 계산을 완료할 수 있는 것은 아니다. 프로그래밍 분야에서 무한 루프라고 불리는 것과 같은 것으로, 계산이 멈추지 않는 경우도 있다. 계산 이론에서는 그러한 가능성이 있는 것을 절차라고 부르며, 유한한 시간 내에 반드시 정지하는 알고리즘과 구별하는 경우가 있다. 여기서, 계산이 멈추는지 여부라는 판정 문제를 미리 결정하는 절차가 없다는 것이 정지 문제가 증명하는 바이다.

정지 문제의 부정적인 결론은 '''계산 가능'''의 한계를 보여준다. 그러나 어떤 의미에서는 당연한 결과이다. 예를 들어, “이러한 조건을 만족하는 자연수는 존재하지 않는다”는 형태의 미해결 수학 문제가 있다고 하자. 자연수는 1, 2, 3, …^영어과 같이 열거할 수 있으며, 수학 문제에 있는 “이러한 조건을 만족하는”과 같은 조건은 컴퓨터 프로그램의 수식과 조건 판단으로 기술할 수 있을 것이다. 만약 어떤 컴퓨터 프로그램이든 정지하는지 여부를 판정할 수 있다면, “그 조건을 만족하는 자연수를 찾으면 정지한다”는 프로그램이 정지하는지 여부를 판정함으로써 그러한 수학 문제를 해결할 수 있게 된다. 그렇게 생각하면 정지 문제의 결론이 부정적인 것은 당연하다고 할 수 있다.

5. 정의

계산 이론에서 어떤 계산 시스템이 모든 튜링-계산 가능 함수를 계산할 수 있으면 '튜링 완전'(Turing-complete) 또는 '튜링 강력'하다고 한다. 이는 범용 튜링 기계를 시뮬레이션할 수 있는 시스템을 말한다.

튜링 완전 시스템은 그것이 계산할 수 있는 모든 함수가 튜링 계산 가능한 경우 튜링 동등하다고 한다. 즉, 튜링 기계와 정확히 같은 함수 집합을 계산한다. 다른 방식으로 표현하면, 튜링 동등 시스템은 범용 튜링 기계를 시뮬레이션할 수 있고, 동시에 범용 튜링 기계에 의해 시뮬레이션될 수 있는 시스템이다. 알려진 모든 물리적으로 구현 가능한 튜링 완전 시스템은 튜링 동등하며, 이는 처치-튜링 명제를 뒷받침한다.^[9]

어떤 시스템의 클래스에 대해, 그 시스템이 해당 클래스의 시스템으로 계산 가능한 모든 함수를 계산할 수 있거나(또는 그러한 각 시스템을 시뮬레이션할 수 있는 경우) 그 시스템을 보편적이라고 한다. 일반적으로 '보편성'이라는 용어는 암묵적으로 튜링 완전 시스템 클래스와 관련하여 사용된다. '약하게 보편적인'이라는 용어는 때때로 (예: 셀룰라 오토마타) 표준 튜링 기계의 정의를 수정하여 무한히 많은 1을 포함하는 입력 스트림을 포함하도록 함으로써 보편성을 달성하는 시스템을 구분하는 데 사용된다.

6. 비수학적 용법

구어체에서 "튜링 완전(Turing-complete)"과 "튜링 등가(Turing-equivalent)"라는 용어는 어떤 실제 세계의 범용 컴퓨터나 컴퓨터 언어도 다른 어떤 실제 세계의 범용 컴퓨터나 컴퓨터 언어의 계산 측면을 근사적으로 시뮬레이션할 수 있음을 의미하는 데 사용된다. 실제로 이것은 컴퓨팅 가상화와 에뮬레이션의 실용적인 개념으로 이어진다.

지금까지 만들어진 실제 컴퓨터는 단일 테이프 튜링 기계(메모리에 "테이프"를 사용하는)처럼 기능적으로 분석될 수 있다. 따라서 그 작동을 충분히 추상화함으로써 관련 수학을 적용할 수 있다. 그러나 실제 컴퓨터는 물리적 자원이 제한되어 있으므로 선형 제한 오토마타 완전(linear bounded automaton complete)만 하다. 반대로, 범용 컴퓨터의 추상화는 튜링 완전 명령어 집합, 무한한 메모리 및 무한한 사용 가능 시간을 갖춘 장치로 정의된다.

7. 디지털 물리학

알려진 모든 물리 법칙은 디지털 컴퓨터에서 일련의 근삿값을 통해 계산 가능한 결과를 낳는다. 디지털 물리학이라는 가설은 이것이 우연이 아니며, 우주 자체가 튜링 완전 기계에서 계산 가능하기 때문이라고 주장한다. 이는 튜링 완전 기계보다 더 강력한 컴퓨터는 물리적으로 만들 수 없다는 것을 의미한다.^[12]

8. 예시

파스칼, C++, XSLT 등은 튜링 완전한 프로그래밍 언어의 예시이다. "튜링 완전"과 "튜링 등가"라는 용어는 어떤 범용 컴퓨터나 컴퓨터 언어가 다른 범용 컴퓨터나 언어의 계산 측면을 시뮬레이션할 수 있음을 의미하며, 이는 컴퓨팅 가상화와 에뮬레이션 개념으로 이어진다.

실제 컴퓨터는 물리적 자원 제약으로 선형 제한 오토마타만 완전하지만, 범용 컴퓨터는 튜링 완전 명령어 집합, 무한한 메모리와 시간을 가진 장치로 정의된다.

람다 대수, μ 재귀 함수, 마르코프 알고리즘 등도 튜링 완전한 계산 모델이다. 람다 대수의 튜링 완전성은 Y 조합자를 통한 재귀 기능에서 비롯되며, 이는 루프와 동등한 능력을 제공한다.

처치-튜링 명제는 튜링 완전성과 관련된 중요한 주제이다.

스티븐 울프럼은 2상태 3기호 튜링 기계 ("2, 3 튜링 기계")의 보편성 증명에 25,000달러의 상금을 걸었고, 버밍엄 대학교 학생 알렉스 스미스가 증명을 제출하여 상금을 받았다.^[38] 매슈 쿡은 규칙 110이 튜링 완전함을 증명했다.

8. 1. 의도되지 않은 튜링 완전성

일부 소프트웨어와 비디오 게임은 우연히, 즉 의도적으로가 아니라 튜링 완전하다.

9. 튜링 불완전 언어

많은 계산 언어는 튜링 완전하지 않다. 그러한 예로 정규 언어 집합이 있는데, 이는 정규 표현식에 의해 생성되고 유한 오토마타에 의해 인식된다. 유한 오토마타보다 강력하지만 여전히 튜링 완전하지 않은 확장은 푸시다운 오토마타와 맥락 자유 문법 범주이며, 이는 프로그램 컴파일의 초기 단계에서 구문 트리를 생성하는 데 일반적으로 사용된다. 다른 예로는 Direct3D 및 OpenGL 확장에 포함된 초기 버전의 픽셀 셰이더 언어 중 일부가 있다.

전체 함수형 프로그래밍 언어(예: Charity, Epigram)에서는 모든 함수가 전체 함수이며 반드시 종료되어야 한다. Charity는 범주론을 기반으로 하는 형식 시스템과 제어 구조를 사용하는 반면, Epigram은 종속 타입을 사용한다. LOOP 언어는 원시 재귀 함수만 계산하도록 설계되었다. 이러한 언어들은 모두 전체 계산 가능 함수의 적절한 부분 집합을 계산한다. 전체 계산 가능 함수의 전체 집합은 계산 가능 열거 가능하지 않기 때문이다. 또한 이러한 언어의 모든 함수는 전체 함수이므로, 재귀 열거 가능 집합에 대한 알고리즘은 튜링 기계와 달리 이러한 언어로 작성할 수 없다.

비록 (비형식) 람다 대수는 튜링 완전하지만, 단순 형식화 람다 대수는 튜링 완전하지 않다.

참조

_[1] 서적 Understanding Computation: From Simple Machines to Impossible Programs https://books.google[...] O'Reilly Media, Inc.
_[2] 서적 To Halt Or Not To Halt? That Is The Question https://books.google[...] World Scientific
_[3] 논문 Programming Paradigms, Turing Completeness and Computational Thinking 2020-02-14
_[4] 서적 Introduction to Programming Concepts with Case Studies in Python https://books.google[...] Springer Science & Business Media
_[5] 서적 The Structure of Intelligence: A New Mathematical Model of Mind https://books.google[...] Springer Science & Business Media
_[6] 서적 Artificial Intelligence: An Introduction https://books.google[...] Routledge
_[7] 서적 Programming Language Design and Implementation https://books.google[...] Springer Nature
_[8] 서적 Genetic Programming: 6th European Conference, EuroGP 2003, Essex, UK, April 14-16, 2003. Proceedings, Volume 6 https://books.google[...] Springer Science & Business Media
_[9] 서적 Alan Turing: The Enigma Burnett Books
_[10] 논문 How to make Zuse's Z3 a universal computer https://www.research[...]
_[11] 논문 Konrad Zuse und der bedingte Sprung 2014-02-01
_[12] 논문 A computer scientist's view of life, the universe, and everything https://doi.org/10.1[...] Springer 2022-05-23
_[13] 웹사이트 Cyclic Tag System https://wiki.postgre[...] 2011-08-08
_[14] 웹사이트 Universal Turing Machine in XSLT https://unidex.com/t[...] 2001-03-30
_[15] 기술보고서 A Mechanical Proof of the Turing Completeness of Pure Lisp https://cs.utexas.ed[...] 1983-05-01
_[16] 서적 Parallel programming: for multicore and cluster systems https://books.google[...] Springer 2013
_[17] 웹사이트 Announcing LAMBDA: Turn Excel formulas into custom functions https://techcommunit[...] 2020-12-03
_[18] 웹사이트 Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine https://themarysue.c[...] 2010-04-16
_[19] 웹사이트 Cities: Skylines Map Becomes A Poop-Powered Computer https://kotaku.com/c[...] 2019-07-16
_[20] 웹사이트 Opus Magnum player makes an alchemical computer https://rockpapersho[...] 2017-11-20
_[21] 웹사이트 This 8-bit processor built in Minecraft can run its own games https://pcworld.com/[...] 2022-07-21
_[22] 학회 Magic: The Gathering Is Turing Complete https://cs.emis.de/L[...]
_[23] 웹사이트 It's possible to build a Turing machine within Magic: The Gathering https://arstechnica.[...] 2019-06-23
_[24] 웹사이트 Infinite versions of minesweeper are Turing complete https://web.mat.bham[...] 2007-05-31
_[25] 웹사이트 Habbo's Twitter thread on the implementation of a Turing machine inside the game. https://twitter.com/[...] 2020-11-09
_[26] 서적 Effective C++ : 55 specific ways to improve your programs and designs https://archive.org/[...] Addison-Wesley 2005
_[27] 학회 Control-flow bending: on the effectiveness of control-flow integrity https://dl.acm.org/d[...] 2015-08-01
_[28] 웹사이트 TypeScript and Turing Completeness https://itnext.io/ty[...] LINKIT 2021-09-23
_[29] 웹사이트 mov is Turing-complete https://stedolan.net[...]
_[30] 웹사이트 One Instruction To Rule Them All: C Compiler Emits Only MOV https://hackaday.com[...] 2021-03-21
_[31] Youtube Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher Domas https://youtube.com/[...] 2015-09-25
_[32] 논문 Using Strand Displacing Polymerase To Program Chemical Reaction Networks 2020-05-04
_[33] 논문 Programmable chemical controllers made from DNA 2013-10-01
_[34] 논문 Enzyme-free nucleic acid dynamical systems 2017-12-15
_[35] 논문 DNA as a universal substrate for chemical kinetics 2010-03-23
_[36] 논문 A Mechanical Turing Machine: Blueprint for a Biomolecular Computer https://wisdom.weizm[...] Weizmann Institute of Science 1999-12-07
_[37] 텍스트
_[38] 웹사이트 Wolfram 2,3 Turing Machine Research Prize: The Solution https://www.wolframs[...] Stephen Wolfram, LLC 2011-11-06