튜링 완성도 란?

튜링 완성도는 프로그래밍 언어가 튜링 기계의 기능을 수행 할 수있는 경우입니다. 이것은 컴퓨터로 간주 될 수있는 가장 단순한 기계라고도하는 매우 기본적인 기계식 컴퓨터의 개념입니다. 오늘날 사용되는 거의 모든 프로그래밍 언어와 이론적으로이를 실행하는 컴퓨터는 튜링 완성도를 갖습니다.

Turing 완전성의 개념은 2 차 세계 대전 중에 암호화 된 메시지를 해독하는 영국 컴퓨터 과학자 Alan Turing의 아이디어입니다. 컴퓨팅에 관한 그의 작업 중에는 컴퓨터가 실제로 할 수있는 일의 철학을 개발하는 것이있었습니다. 여기에는 알고리즘을 실행하여 컴퓨터가 간단하게 작동한다는 개념이 포함되었습니다. 즉, 데이터를 처리하고 문제를 해결하기 위해 고정 된 규칙 세트를 따릅니다. 이것은 컴퓨터가 사람의 생각처럼 "생각"하거나 결정을 내리지 않음을 의미합니다.

개념을 설명하기 위해 튜링은 자신이 "a-machine"이라고하는 가상 머신을 설명했습니다. 다른 사람들은 나중에 그것을 튜링 기계라고 불렀습니다. 기계는 앞뒤로 움직일 수 있고 한 줄의 기호를 포함 할 수있는 테이프 릴을 처리합니다. 기계는 언제든지 하나의 기호를 처리하고 필요한 경우 변경할 수 있습니다. 이 개념의 목적 상 테이프 릴은 무한정 길 수 있습니다. 즉 컴퓨터의 메모리가 본래 제한되지 않았습니다. 이것은 컴퓨터에 따라야 할 지침 세트가 있으면 해당 지침을 적용 할 수있는 데이터의 양에는 물리적 한계가 있다는 아이디어와 유사합니다.

아이러니하게도 오늘날 대부분의 컴퓨터에는 실제로 튜링 완전성이 없습니다. 사용 가능한 저장 공간과 처리 할 수있는 데이터에 제한이 있기 때문입니다. 그들은 또한 신체적 한계가 있으며, 특히 그들은 결국 마모 될 것입니다. 실제로 Turing 완성도를 갖는 프로그래밍 언어입니다. 이 때문에 이러한 프로그램을 실행하는 컴퓨터는 Turing 컴퓨터가 아니지만 시뮬레이션하는 데 사용할 수 있습니다.

튜링 완성도를 튜링 테스트와 혼동해서는 안됩니다. 이것은 컴퓨터가 자연 언어로 대화 할 수 있는지 확인하기 위해 Turing이 고안 한 실험이었습니다. 테스트의 원칙은 사람이 컴퓨터와 다른 사람과의 텍스트 대화를 구별 할 수 없으면 컴퓨터가 테스트를 통과한다는 것입니다. 대화 대상의 범위가 제한되어있을 때 일부 컴퓨터는 테스트를 통과했지만 무제한 대화에서는 그렇게하지 않았습니다.