튜링 완전성

Turing completeness
오라클 기계의 상대적 계산 가능성 이론에서 이 용어를 사용하려면 튜링 축소를 참조하십시오.

계산 가능성 이론에서 데이터 조작 규칙의 시스템(예: 계산 모델, 컴퓨터의 명령어 세트, 프로그래밍 언어 또는 셀룰러 오토마톤)은 어떤 튜링 기계(영국 수학자이자 컴퓨터 과학자인 앨런 튜링이 고안한)를 시뮬레이션하는 데 사용할 수 있다면 튜링 완전 또는 계산적으로 보편적이라고 말합니다. 즉, 이 시스템은 다른 데이터 조작 규칙 집합을 인식하거나 결정할 수 있습니다. 튜링 완성도는 이러한 데이터 조작 규칙 집합의 힘을 표현하는 방법으로 사용됩니다. 오늘날 사실상 모든 프로그래밍 언어는 튜링이 완성된 언어입니다.

이와 관련된 개념은 튜링 등가의 개념인데, P가 Q를, Q가 P를 모의실험할 수 있다면 두 대의 컴퓨터 P와 Q를 동등하다고 합니다. 처치-튜링 논문은 알고리즘으로 값을 계산할 수 있는 함수는 튜링 기계로 계산할 수 있으며, 따라서 실제 컴퓨터가 튜링 기계를 시뮬레이션할 수 있다면 튜링 기계와 동등하다고 추측합니다. 범용 튜링 머신은 모든 튜링 머신을 시뮬레이션하고 가능한 실제 컴퓨터의 순수 계산 측면을 확장하는 데 사용될 수 있습니다.

어떤 것이 튜링-완전하다는 것을 보여주기 위해, 그것이 어떤 튜링-완전 시스템을 시뮬레이션하는 데 사용될 수 있다는 것을 보여주기에 충분합니다. 어떤 물리적 시스템도 무한한 메모리를 가질 수 없지만, 유한한 메모리의 한계를 무시한다면, 대부분의 프로그래밍 언어는 그렇지 않으면 튜링-완전입니다.

비수학적 용법

구어체 사용에서 "튜링-완전" 및 "튜링-동등" 용어는 실제 범용 컴퓨터 또는 컴퓨터 언어가 다른 실제 범용 컴퓨터 또는 컴퓨터 언어의 계산 측면을 대략적으로 시뮬레이션할 수 있음을 의미하는 데 사용됩니다. 이는 실제 현실에서 컴퓨팅 가상화 및 에뮬레이션의 실용적인 개념으로 이어집니다.[citation needed]

지금까지 구축된 실제 컴퓨터는 (기억을 위해 "테이프"를 사용하는) 단일 테이프 튜링 기계처럼 기능적으로 분석될 수 있으므로 관련 수학은 충분히 그 작동을 추상화하여 적용할 수 있습니다. 그러나 실제 컴퓨터는 물리적 리소스가 제한되어 있으므로 선형 경계 자동화만 완료됩니다. 이와 대조적으로 범용 컴퓨터의 추상화는 튜링-완전 명령어 세트, 무한한 메모리, 무한한 가용 시간을 가진 장치로 정의됩니다.

형식적 정의

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

튜링 완전성
튜링이 계산 가능한 모든 함수를 계산할 수 있는 계산 시스템을 튜링-완전(또는 튜링-파워풀)이라고 합니다. 또는 그러한 시스템은 보편적인 튜링 기계를 시뮬레이션할 수 있는 시스템입니다.
튜링 동치
튜링-완전 시스템은 계산할 수 있는 모든 기능이 튜링 계산 가능하다면 튜링 등가 시스템이라고 합니다. 즉, 튜링 기계와 정확히 동일한 종류의 기능을 계산합니다. 또는 보편적인 튜링 기계를 시뮬레이션하고 시뮬레이션할 수 있는 시스템이 튜링 등가 시스템입니다. (물리적으로 구현 가능한 모든 알려진 튜링 완전 시스템은 튜링 등가이며, 이는 교회-튜링 논문을 뒷받침합니다.)[citation needed]
(전산)보편성
시스템이 해당 클래스의 시스템에서 계산 가능한 모든 기능을 계산할 수 있는 경우(또는 각 시스템을 시뮬레이션할 수 있는 경우) 시스템 클래스와 관련하여 범용이라고 합니다. 일반적으로 '보편성'이라는 용어는 튜링이 완성한 시스템 클래스와 관련하여 암묵적으로 사용됩니다. "약하게 보편적인"이라는 용어는 무한히 많은 1을 가진 입력 스트림을 포함하도록 튜링 기계의 표준 정의를 수정함으로써만 보편성이 달성되는 시스템(예: 셀룰러 오토마톤)을 구별하는 데 사용되기도 합니다.

역사

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

찰스 배비지(Charles Babbage)의 분석 엔진(1830년대)은 만약 그것이 설계된 당시에 만들어졌더라면 최초의 튜링 완성 기계였을 것입니다. 배비지(Babbage)는 이 기계가 원시적인 논리적 추론을 포함한 엄청난 계산의 위업을 수행할 수 있다는 것을 높이 평가했지만, 다른 어떤 기계도 이보다 더 잘할 수 있다는 것을 높이 평가하지는 않았습니다.[citation needed] 1830년대부터 1940년대까지 덧셈기나 승수와 같은 기계 계산 기계가 만들어지고 개선되었지만, 그것들은 조건부 분기를 수행할 수 없었고, 따라서 튜링-완전이 아니었습니다.

19세기 후반 레오폴드 크로네커는 원시 재귀 함수를 정의하면서 계산 가능성에 대한 개념을 공식화했습니다. 이러한 함수는 원격 계산으로 계산할 수 있지만, 이를 계산하는 명령어는 무한 루프를 허용하지 않기 때문에 보편적인 컴퓨터를 만들기에는 충분하지 않습니다. 20세기 초, 데이비드 힐버트는 기계가 수행할 수 있는 정확한 공리와 정확한 논리적 추론 규칙으로 모든 수학을 공리화하는 프로그램을 이끌었습니다. 얼마 지나지 않아 작은 일련의 공제 규칙만으로도 어떤 공리의 결과를 도출하기에 충분하다는 것이 분명해졌습니다. 이 규칙들은 1930년 쿠르트 괴델에 의해 모든 정리를 만들기에 충분하다는 것이 증명되었습니다.

계산의 실제 개념은 괴델의 불완전성 정리에서 시작하여 얼마 지나지 않아 분리되었습니다. 이 정리는 공리 체계가 그 정리를 추론하는 계산에 대해 추론할 때 제한적이라는 것을 보여주었습니다. 교회와 튜링은 독립적으로 힐베르트의 엔체이둥 문제(결정 문제)가 풀 수 없다는 것을 증명했고,[1] 따라서 불완전성 정리의 계산적 핵심을 확인했습니다. 이 연구는 일반적인 재귀 함수에 대한 괴델의 연구와 함께 단순한 명령어 집합이 있다는 것을 확인했으며, 이를 종합하면 어떤 계산도 생성할 수 있습니다. 괴델의 연구는 계산의 개념이 본질적으로 독특하다는 것을 보여주었습니다.

1941년 콘라드 주세는 Z3 컴퓨터를 완성했습니다. 주세는 당시 튜링의 계산 가능성에 대한 연구에 익숙하지 않았습니다. 특히, Z3는 조건부 점프를 위한 전용 시설이 부족하여 튜링이 완벽하지 못했습니다. 그러나 1998년 로하스는 Z3가 조건부 점프를 시뮬레이션할 수 있다는 것을 보여주었고, 따라서 튜링은 이론적으로 완전하다는 것을 보여주었습니다. 이를 위해서는 테이프 프로그램이 모든 지점의 양쪽을 통해 가능한 모든 경로를 실행하기에 충분히 길어야 합니다.[2]

실제로 조건부 분기가 가능하고 따라서 튜링이 실제로 완성된 최초의 컴퓨터는 1946년 ENIAC였습니다. Zuse의 Z4 컴퓨터는 1945년에 작동했지만 1950년까지 조건부 분기를 지원하지 않았습니다.[3]

계산가능성 이론

계산 가능성 이론은 계산 모델을 사용하여 문제를 분석하고 문제가 계산 가능한지 여부와 어떤 상황에서 계산 가능한지 여부를 결정합니다. 계산 가능성 이론의 첫 번째 결과는 (튜링-완전) 시스템이 임의의 긴 시간 동안 무엇을 할지 예측할 수 없는 문제가 존재한다는 것입니다.

대표적인 예가 중단 문제입니다. 튜링이 완료된 일부 언어로 된 프로그램과 해당 프로그램에 공급할 일부 데이터를 입력으로 받는 알고리즘을 만들고, 입력에 따라 작동하는 프로그램이 결국 중단될 것인지 아니면 영원히 계속될 것인지를 결정합니다. 일부 입력에 대해 이 작업을 수행할 수 있는 알고리즘을 만드는 것은 사소한 일이지만 일반적으로 이 작업을 수행하는 것은 불가능합니다. 프로그램의 최종 출력에 대한 어떤 특성에 대해서도 이 특성이 유지될지 여부를 결정하는 것은 불가능합니다.

이러한 불가능성은 실제 컴퓨터 프로그램을 분석할 때 문제를 제기합니다. 예를 들어, 프로그래머가 무한 루프를 작성하는 것을 완전히 보호하거나 사용자가 무한 루프를 유발할 입력을 공급하는 것을 보호하는 도구를 작성할 수 없습니다.

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

튜링 신탁

주요 기사: 오라클 머신

무한대의 데이터 테이프에 접근할 수 있는 컴퓨터는 튜링 기계보다 더 강력할 수 있습니다. 예를 들어, 테이프에는 중단 문제나 다른 튜링이 결정할 수 없는 문제에 대한 해결책이 포함되어 있을 수 있습니다. 이처럼 무한한 데이터 테이프를 튜링 오라클이라고 합니다. 무작위 데이터가 있는 튜링 오라클도 계산이 불가능합니다(확률 1). 왜냐하면 계산은 셀 수 없이 많지만 오라클은 셀 수 없이 많기 때문입니다. 그래서 무작위 튜링 오라클을 가진 컴퓨터는 튜링 기계가 할 수 없는 것들을 계산할 수 있습니다.

디지털 물리학

참고 항목: 교회-투르팅 논문 § 철학적 함의

알려진 모든 물리 법칙은 디지털 컴퓨터에서 일련의 근사치로 계산할 수 있는 결과를 가져옵니다. 디지털 물리학이라는 가설은 우주 자체가 보편적인 튜링 기계에서 계산 가능하기 때문에 이것이 우연이 아니라고 말합니다. 이것은 보편적인 튜링 기계보다 더 강력한 컴퓨터가 물리적으로 만들어질 수 없다는 것을 의미합니다.[4]

예

튜링-완전 시스템으로 논의되는 계산 시스템(대수, 칼리)은 이론 컴퓨터 과학을 연구하기 위한 것입니다. 계산의 한계를 더 쉽게 이해할 수 있도록 가능한 한 단순화하기 위한 것입니다. 다음은 몇 가지입니다.

대부분의 프로그래밍 언어(유한 메모리가 생략된 특정 구조를 가진 추상적 모델)는 전통적이고 틀에 얽매이지 않는 튜링 완전 언어입니다. 여기에는 다음이 포함됩니다.

일부 재작성 시스템은 튜링이 완벽합니다.

튜링 완전성은 능력을 구현하는 데 사용되는 특정 언어 특징의 처방이 아니라 능력에 대한 추상적인 진술입니다. 튜링의 완전성을 달성하는 데 사용되는 기능은 상당히 다를 수 있습니다. 포트란 시스템은 반복을 달성하기 위해 루프 구조를 사용하거나 문장으로 이동할 수도 있습니다. 하스켈과 프롤로그는 루프가 거의 완전히 없는 재귀를 사용합니다. 대부분의 프로그래밍 언어는 메모리(RAM 및 레지스터)와 제어 장치가 있는 폰 노이만 아키텍처의 계산을 설명합니다. 이 두 가지 요소가 이 아키텍처를 튜링-완전하게 만듭니다. 순수 기능 언어도 튜링이 완성된 언어입니다.[7][8]

선언형 SQL의 튜링 완전성은 재귀적 공통 테이블 식을 통해 구현됩니다. 당연히 SQL(PLSQL 등)에 대한 절차적 확장도 튜링-완전합니다. 이것은 상대적으로 강력한 튜링-완전하지 않은 언어가 드문 한 가지 이유를 보여줍니다: 언어가 처음에 더 강력할수록 적용되는 작업이 더 복잡해지고 완전성 부족이 단점으로 인식되어 튜링-완전할 때까지 확장을 장려합니다.

유형이 지정되지 않은 람다 미적분학은 튜링-완전이지만, 시스템 F를 포함한 많은 유형의 람다 미적분학은 그렇지 않습니다. 타이핑된 시스템의 값은 더 많은 오류를 탐지하면서 가장 일반적인 컴퓨터 프로그램을 표현하는 능력에 기반합니다.

Rule 110과 Conway의 Game of Life는 모두 셀룰러 오토마타로 튜링이 완성된 게임입니다.

의도하지 않은 튜링 완전성

일부 소프트웨어 및 비디오 게임은 우연에 의해 튜링이 완성됩니다. 즉, 설계에 의해 완성되지 않습니다.

소프트웨어:

게임:

소셜 미디어:

계산 언어:

생물학:

비튜링-완전 언어

튜링이 완전하지 않은 많은 계산 언어가 존재합니다. 정규 표현식에 의해 생성되고 유한 오토마타에 의해 인식되는 정규 언어 집합이 그러한 예 중 하나입니다. 유한 오토마타의 더 강력하지만 여전히 튜링 완전하지 않은 확장은 푸시다운 오토마타 및 컨텍스트가 없는 문법 범주이며, 이는 일반적으로 프로그램 컴파일의 초기 단계에서 구문 분석 트리를 생성하는 데 사용됩니다. 추가적인 예로는 Direct3D 및 OpenGL 확장에 내장된 픽셀 셰이더 언어의 초기 버전이 있습니다.[citation needed]

채리티, 에피그램과 같은 토탈 기능 프로그래밍 언어에서는 모든 기능이 토탈이므로 종료해야 합니다. 자선은 유형 체계를 사용하고 범주 이론에 기반한 통제 구조를 사용하는 반면 에피그램은 종속 유형을 사용합니다. LOOP 언어는 원시 재귀적인 함수만을 계산하도록 설계되었습니다. 전체 계산 가능한 함수의 전체 집합은 계산 가능하게 열거할 수 없기 때문에 이러한 모든 것은 전체 계산 가능한 함수의 적절한 하위 집합을 계산합니다. 또한 이 언어들의 모든 함수들은 전체적이기 때문에 재귀적으로 열거할 수 있는 집합에 대한 알고리즘은 튜링 기계와 달리 이 언어들로 작성될 수 없습니다.

(타자되지 않은) 람다 미적분은 튜링이 완전하지만, 단순하게 입력된 람다 미적분은 그렇지 않습니다.

참고 항목

참고문헌

  1. ^ Hodges, Andrew (1992) [1983], Alan Turing: The Enigma, London: Burnett Books, p. 111, ISBN 0-04-510060-8
  2. ^ Rojas, Raul (1998). "How to make Zuse's Z3 a universal computer". Annals of the History of Computing. 20 (3): 51–54. doi:10.1109/85.707574.
  3. ^ Rojas, Raúl (1 February 2014). "Konrad Zuse und der bedingte Sprung" [Konrad Zuse and the conditional jump]. Informatik-Spektrum (in German). 37 (1): 50–53. doi:10.1007/s00287-013-0717-9. ISSN 0170-6012. S2CID 1086397.
  4. ^ Schmidhuber, Jürgen (1997), Freksa, Christian; Jantzen, Matthias; Valk, Rüdiger (eds.), "A computer scientist's view of life, the universe, and everything", Foundations of Computer Science: Potential — Theory — Cognition, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, vol. 1337, pp. 201–208, arXiv:quant-ph/9904050, doi:10.1007/bfb0052088, ISBN 978-3-540-69640-7, S2CID 17830241, retrieved 23 May 2022
  5. ^ Dfetter; Breinbaas (8 August 2011). "Cyclic Tag System". PostgreSQL wiki. Retrieved 10 September 2014.
  6. ^ Lyons, Bob (30 March 2001). "Universal Turing Machine in XSLT". B2B Integration Solutions from Unidex. Archived from the original on 17 July 2011. Retrieved 5 July 2010.
  7. ^ Boyer, Robert S.; Moore, J. Strother (May 1983). A Mechanical Proof of the Turing Completeness of Pure Lisp (PDF) (Technical report). Institute for Computing Science, University of Texas at Austin. 37. Archived (PDF) from the original on 22 September 2017.
  8. ^ Rauber, Thomas; Rünger, Gudula (2013). Parallel programming: for multicore and cluster systems (2nd ed.). Springer. ISBN 9783642378010.
  9. ^ "Announcing LAMBDA: Turn Excel formulas into custom functions". TECHCOMMUNITY.MICROSOFT.COM. 3 December 2020. Retrieved 8 December 2020.
  10. ^ Cedotal, Andrew (16 April 2010). "Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine". The Mary Sue. Archived from the original on 27 June 2015. Retrieved 2 June 2015.
  11. ^ Plunkett, Luke (16 July 2019). "Cities: Skylines Map Becomes A Poop-Powered Computer". Kotaku. Retrieved 16 July 2019.
  12. ^ Caldwell, Brendan (20 November 2017). "Opus Magnum player makes an alchemical computer". Rock Paper Shotgun. Retrieved 23 September 2019.
  13. ^ Crider, Michael. "This 8-bit processor built in Minecraft can run its own games". PCWorld. Retrieved 21 July 2022.
  14. ^ Churchill, Alex; Biderman, Stella; Herrick, Austin (2020). Magic: The Gathering Is Turing Complete (PDF). 10th International Conference on Fun with Algorithms.
  15. ^ Ouellette, Jennifer (23 June 2019). "It's possible to build a Turing machine within Magic: The Gathering". Ars Technica. Retrieved 12 March 2023.
  16. ^ Kaye, Richard (31 May 2007). "Infinite versions of minesweeper are Turing complete" (PDF). Archived from the original (PDF) on 3 August 2016. Retrieved 8 July 2016.
  17. ^ "Habbo's Twitter thread on the implementation of a Turing machine inside the game". 9 November 2020. Retrieved 11 November 2020.
  18. ^ Meyers, Scott (Scott Douglas) (2005). Effective C++ : 55 specific ways to improve your programs and designs (3rd ed.). Upper Saddle River, NJ: Addison-Wesley. ISBN 0321334876. OCLC 60425273.
  19. ^ 제27회 IOCCC 우승자
    Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David; Gross, Thomas R. (August 2015). "Control-flow bending: on the effectiveness of control-flow integrity". Proceedings of the 24th USENIX Conference on Security Symposium. pp. 161–176. ISBN 9781931971232.
  20. ^ Dabler, Ryan (23 September 2021). "TypeScript and Turing Completeness". ITNEXT. LINKIT. Retrieved 12 November 2022.
  21. ^ Dolan, Stephen. "mov is Turing-complete" (PDF). stedolan.net. Archived from the original (PDF) on 14 February 2021. Retrieved 9 May 2019.
  22. ^ Williams, Al (21 March 2021). "One Instruction To Rule Them All: C Compiler Emits Only MOV". Hackaday. Retrieved 23 October 2023.
  23. ^ Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher Domas, retrieved 5 November 2022
  24. ^ Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis; Strauss, Karin; Chen, Yuan-Jyue; Reif, John (4 May 2020). "Using Strand Displacing Polymerase To Program Chemical Reaction Networks". Journal of the American Chemical Society. 142 (21): 9587–9593. doi:10.1021/jacs.0c02240. ISSN 0002-7863. PMID 32364723. S2CID 218504535.
  25. ^ Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (October 2013). "Programmable chemical controllers made from DNA". Nature Nanotechnology. 8 (10): 755–762. Bibcode:2013NatNa...8..755C. doi:10.1038/nnano.2013.189. ISSN 1748-3395. PMC 4150546. PMID 24077029.
  26. ^ Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (15 December 2017). "Enzyme-free nucleic acid dynamical systems". Science. 358 (6369): eaal2052. doi:10.1126/science.aal2052. ISSN 0036-8075. PMID 29242317.
  27. ^ Soloveichik, David; Seelig, Georg; Winfree, Erik (23 March 2010). "DNA as a universal substrate for chemical kinetics". Proceedings of the National Academy of Sciences. 107 (12): 5393–5398. Bibcode:2010PNAS..107.5393S. doi:10.1073/pnas.0909380107. ISSN 0027-8424. PMC 2851759. PMID 20203007.
  28. ^ Shapiro, Ehud (7 December 1999). "A Mechanical Turing Machine: Blueprint for a Biomolecular Computer". Interface Focus. Weizmann Institute of Science. 2 (4): 497–503. doi:10.1098/rsfs.2011.0118. PMC 3363030. PMID 22649583. Archived from the original on 3 January 2009. Retrieved 13 August 2009.

추가읽기

외부 링크