diagonalization
모든 기계와 적어도 한 군데서 다르게 답하는 문제를 만들어 내는 증명법
가능한 기계를 모두 한 줄로 늘어놓고, i 번째 기계가 i 번째 입력에 내는 답과 반대로 답하도록 문제를 정의해 그 어떤 기계로도 풀리지 않게 만드는 방법이다. 칸토어가 실수가 자연수보다 많음을 보일 때 처음 썼고, 튜링의 정지 문제 증명과 시간 위계 정리가 이 방법을 쓴다. P 와 EXP 를 가르는 데는 성공했지만, 이 방법은 상대화되므로 그것만으로는 P 와 NP 를 가를 수 없다.