튜링머신

 튜링은 먼저 기계적인 계산에 대하여 증명을 내렸다. 그는 정해진 부품박스에 부품을 빼다가 써서 그것을 가지고 연산을 하는 것이 기계적인 방식이라고 증명을 내렸다. 그 후 이것으로 모든 참인 수리명제를 이끌어낸다는 것은 불가능하다는 것을 증명하였다.

 이 기계를 튜링머신이라고 불렀는데, 튜링머신은 다음을 가지고 연산을 하는 기계이다.

무한한 길이의 테이프를 준비한다. (이 테이프는 하나의 문자를 쓸 수 있는 칸이 일정하게 나눠져있다)

그 후 테이프를 쓰는 유한한 심볼을 준비한다.

또, 유한한 규칙표를 준비한다.

 이것으로 기계를 움직이는 준비가 끝났다. 기계는 테이프에 있는 하나의 심볼을 읽고 쓸 수 있는 헤더와 기계의 현재 상태로 나눠져 있다.

 규칙표에는 현재 기계의 상태와 헤더가 위치한 테이프에 기록되 읽은 심볼 그후 쓸 심볼 그리고 어디로 가야할지, 기계는 어떤 상태를 나타낼지가 적혀있다. 

위에 사진에 나타난 기계로 예를 들어 살펴보자.

현재 기계의 상태는 A이고, 읽은 기호는 *이므로 *을 그대로 *로 쓰고 두 번째 칸으로 헤드를 옮기며 기계의 상태를 A라 둔다.

두 번째 칸에서 기계의 상태는 A이고, 읽은 기호는 $이므로 $를 그대로 쓰고 세 번째 칸으로 헤드를 옮기며 기계의 상태를 B라 둔다.

세 번째 칸에서 기계의 상태는 B이고, 읽은 기호는 *이므로 *을 그대로 쓰고 세 번째 칸으로 헤드를 옮기며 기계의 상태를 C라 둔다.

다시 두 번째 칸에서 기계의 상태는 C이고, 읽은 기호는 $이므로 *를 쓰고 세 번째 칸으로 헤드를 옮기며 기계의 상태를 C라 둔다.

세 번째 칸에서 기계의 상태는 C이고, 읽은 기호는 *이므로 $를 쓰고 네 번째 칸으로 헤드를 옮기며 기계의 상태를 B라 둔다.

...

 위 연산을 계속하면 테잎안에 내용은 이렇게 바뀐다.

그렇다 이 규칙표는 $를 맨 오른쪽에 보내는 규칙이었다. 이 기계는 현대에 컴퓨터와 유사한 역할을 한다.