튜링 완전이란 무엇인가?

Turing Machine

• 가상의 기계
• 무한히 긴 테이프
• 그 테이프를 읽고 쓰는 헤드
• 상태 머신 (현재 상태와 입력 문자를 기반으로 다음 상태와 출력 문자를 결정)
• "이론상으로 모든 계산을 수행할 수 있음"

Turing Completeness system

• 튜링 기계가 할 수 있는 모든 계산을 수행할 수 있는 시스템를 말함
• 언어로는 C, Java, Python, Ruby, JavaScript 등이 있음

Turing Incompleteness system

• 튜링 완전하지 않은 언어를 말함
• 특정한 종류의 계산을 수행할 수 없음
• 유한 상태 기계에서는 튜링 완전한 시스템을 만들 수 없음
• 튜링 불완전할 경우, 특정 계산만을 처리할 수 있기 때문에 보안상의 강점을 가짐

Reference

• 튜링 완전
• 튜링 기계