알고리즘의 불완전성

 

불완전성의 원리

 

(1) 자연수의 사칙연산을 포함하는 어떠한 공리계도 무모순인 동시에 완전할 수 없다. 어떤 체계가 무모순이라면, 그 체계에서는 참이면서도 증명할 수 없는 명제가 존재한다.

 

(2) 자연수의 사칙연산을 포함하는 어떠한 공리계가 무모순일 경우, 그 공리계는 자기 자신의 무모순에 대한 정리를 포함할 수 없다.

 

 

 

알고리즘 Vs 불완전성의 원리 

 

알고리즘 : 스스로 계산하는 논리적 체계

불완전성의 원리 : 알고리즘은 스스로 논리적으로 완전함을 증명할 수 없다