튜링 기계

칸으로 나뉜 끝없는 테이프, 한 칸씩 읽고 쓰며 움직이는 머리, 유한한 상태와 규칙표로 이루어진 가상의 기계다. 앨런 튜링이 1936년에 내놓았다. 알고리즘으로 계산할 수 있는 것은 모두 튜링 기계로 계산할 수 있다고 보며(처치–튜링 논제), 계산 시간은 기계가 움직인 단계 수로 정의한다. 실제 컴퓨터와 튜링 기계는 서로를 다항 시간 차이 안에서 흉내 낼 수 있어서, P 와 NP 의 정의는 어느 쪽을 써도 달라지지 않는다. Clay 수학연구소의 공식 문제 기술도 튜링 기계로 P 대 NP 문제를 정의한다.