완전성은 무엇입니까?

완전성은 프로그래밍 언어가 튜링 머신의 기능을 수행 할 수있을 때입니다. 이것은 매우 기본적인 기계식 컴퓨터의 개념으로, 때로는 컴퓨터로 간주 될 수있는 가장 간단한 기계로 묘사됩니다. 오늘날 사용중인 거의 모든 프로그래밍 언어와 이론적으로는 이론적으로이를 운영하는 컴퓨터는 완전성을 가지고 있습니다.

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

개념을 설명하기 위해튜링은 "A"가 자동으로 서있는 "a-machine"이라고 불리는 가상의 기계를 묘사했다. 다른 사람들은 나중에 그것을 튜링 머신이라고 불렀습니다. 이 기계는 테이프 릴을 처리하여 뒤로 또는 앞으로 움직일 수 있고 기호 줄이 포함되어 있습니다. 언제라도 기계는 하나의 기호를 처리하고 필요한 경우 변경할 수 있습니다. 개념의 목적 상, 테이프 릴은 무한히 길어질 수 있으며, 이는 컴퓨터의 기억이 본질적으로 제한되지 않았다는 것을 의미합니다. 이것은 컴퓨터에 따라야 할 일련의 지침이 있으면 해당 지침을 적용 할 수있는 데이터의 양은 물리적 한계에만 적용된다는 아이디어의 비유입니다.

.

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

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