튜링 완전

1 개요

turing completeness

turing 完全

튜링 완전, 튜링 완전성

• 어떤 프로그래밍 언어나 추상 기계가 튜링 기계와 동일한 계산 능력을 가진다는 것
• 이것은 튜링 머신으로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 기계로 풀 수 있다는 의미이다.
• 제한 없는 크기의 메모리를 갖는 기계를 만드는 것이 불가능하므로, 진정한 의미의 튜링 완전 기계는 아마도 물리적으로 불가능할 것이다. 그러나, 제한 없이 기억 장치의 크기를 늘려갈 수 있다고 가정할 수 있는 물리적인 기계 혹은 프로그래밍 언어에 대해서는, 느슨하게 튜링 완전하다고 간주한다. 이런 맥락에서, 요즘 나온 컴퓨터들은 튜링 완전하다고 여겨지고 있다.

2 같이 보기

• 튜링
• 완전
• 가상화
• 튜링 기계
• 튜링 테스트
• 촘스키 위계
• 처치-튜링 논제
• 계산가능성 이론
• 알고리즘 정보 이론

3 참고

• 위키백과 "튜링 완전"
• 위키낱말사전 "튜링 완전"
• 다음사전 "튜링 완전"
• 다음백과 "튜링 완전"
• 네이버사전 "튜링 완전"
• 네이버백과 "튜링 완전"
• 나무위키 "튜링 완전"
• 리브레 위키 "튜링 완전"