첫번째 형태

두번째 형태

자연수 집합을 로 정의하자. 모든 에 대해 함수 를 계산하는 알고리즘이 있을 때 가 계산 가능하다고 한다. 여기서 알고리즘에는 계산을 완료하는 데 필요한 시간이나 공간에 대한 제한이 없는 것으로 가정한다. 마지막으로, 다음 특성 함수가 계산 가능할 때 집합 가 계산 가능하다고 한다.

의 치역 가 계산 불가능하도록 하는 계산 가능한 함수 가 존재한다.

계산 가능성 이론은 불완전성이 사소한 속임수에 의존하지 않는 만연한 기본 속성이라는 관점을 제공한다. 이러한 관점에서 논리학자가 연구하는 형식 체계는 단순히 계산 가능한 함수로서 정리(더 정확하게는 정리의 괴델 수)를 토해내는 것이다. 이러한 체계는 일반적으로 일련의 공리와 추론 규칙의 관점에서 주어진다. 그런 다음 공리에서 시작하여 추론 규칙을 반복적으로 적용하여 진행하는 알고리즘을 떠올릴 수 있다. 불완전성 정리의 형태를 도출하기 위해, 위 정리에서 정의한 집합 와 명제 로부터 시작하자. 이때, 은 고정된 자연수이다. 이 명제를 라고 부르자. 자연수 이 주어질 때 명제 을 도출하는 알고리즘이 있다고 가정하기만 하면 된다. 형식 체계를 나타내기 위해 기호 를 사용하자. 는 다음 조건을 만족할 때 건전(sound)하다고 한다.

특정 자연수 에 대해 이면, 이다.

이 단지 명제 를 나타내기 때문에, 건전성은 단지 증명가능한 명제가 참임을 뜻한다.

다시 말하자면, 참이면서 증명 불가능한 명제가 있다는 것이다. 우린 그저 특정 의 값을 바꾸는 데에만 성공했음을 명심해라.