완전고용정리

컴퓨터 과학과 수학에서 완전고용정리는 어떤 알고리즘도 일부 전문가 계층에 의해 수행되는 특정 업무를 최적으로 수행할 수 없다는 것을 기술하는 정리를 가리키기 위해 종종 유머러스하게 사용되는 용어다.그러한 정리가 적어도 어떤 특정한 작업이 수행되는 방식을 개선하기 위해 새로운 기법을 계속 발견하는 무한한 범위가 있다는 것을 보증하기 때문에 생겨난 이름이다.

예를 들어, 컴파일러 작성자에 대한 완전한 고용 정리는 컴파일러에 대한 그러한 증거는 비지속적인 계산을 감지하고 그것들을 1개의 계통 무한 루프로 줄여야 하기 때문에, 틀림없이 완벽한 크기 최적 컴파일러와 같은 것은 없다고 명시한다.따라서 크기 최적화 컴파일러의 존재는 존재할 수 없는 중단 문제에 대한 해결책을 암시할 수 있다.이것은 또한 최고의 컴파일러를 가지고 있다는 증거가 존재할 수 없기 때문에 항상 더 나은 컴파일러가 있을 수 있다는 것을 암시한다.따라서, 컴파일러 작가들은 항상 그들이 개선해야 할 것이 있다고 추측할 수 있을 것이다.실용적인 컴퓨터 과학에서 비슷한 예로 효율적인 범용 해결사는 존재할 수 없으며, 따라서 가장 잘 알려진 해결책이 개선될 수 있는 어떤 특정한 문제가 항상 있을 것이라는 검색과 최적화에 공짜 점심을 제공하지 않는다는 생각을 들 수 있다.

마찬가지로 괴델의 불완전성 이론은 수학자들에게 완전 고용 이론이라고 불려왔다.바이러스 작성과 검출, 스팸 필터링과 필터 파손 등의 업무도 라이스의 정리 대상이 된다.

참조

• 솔로몬오프, 레이, "유도 추론의 일반 이론에 관한 예비 보고서", 보고서 V-131, 케임브리지, 케임브리지, 제토르 주식회사, 1960년 2월 4일.
• 페이지 401, ML에서의 모던 컴파일러 구현, 1998년 캠브리지 대학 출판부 앤드류 W. 애펠. ISBN0-521-58274-1.
• 페이지 27, 임베디드 시스템용 리타겟 컴파일러 기술: 도구 및 응용 프로그램, 레이너 르우퍼스와 스프링거-베를랙의 피터 마웨델, 2001.ISBN 0-7923-7578-5.
• 펜실베니아 대학의 현대 프로그래밍 언어 강좌의 참고 사항 8 페이지 참조.