SD는 숫자이기 때문에 튜링 머신의 테이프에 기록될 수 있습니다. 이 숫자는 이진수나 십진수, 혹은 다른 방식으로도 인코딩할 수 있습니다. 튜링은 자신의 기호에 맞게 1, 2, 3, 5, 7이라는 숫자를 조합하여 SD를 인코딩했습니다.

다음으로 튜링은 테이프에 기록된 SD를 실행할 수 있는 프로그램을 작성했습니다. 이 프로그램은 일종의 범용 계산 기계(universal computing machine)이며, 여기에서는 U라고 부르겠습니다. 이제 SD가 인코딩된 테이프에 프로그램 U를 실행하면 그 SD에 인코딩된 프로그램의 수행 결과가 테이프 빈 공간에 출력됩니다.

상태 전이표를 실행하는 프로그램을 작성한 적이 있다면 U는 바로 그런 종류의 프로그램입니다. U는 SD를 읽으면서 현재 상태와 기호에 일치하는 전이 행을 찾고, 그 행에 지정된 동작을 수행하기만 하면 됩니다. 아주 간단합니다.

튜링은 이런 개념들을 이용하여 어떤 임의의 SD가 특정한 동작을 할지 말지를 유한한 시간 내에 판별해 낼 수 있는 프로그램 D는 존재하지 않음을 증명했습니다. 이 증명에 대한 자세한 내용은 이 책 범위를 넘는 것이기에 더 이상 다루지 않습니다.

이제 우리 프로그래머 관점에서 볼 때, 튜링이 발명한 것은 바로 프로그램 내장식 컴퓨터입니다. SD는 테이프에 저장된 프로그램이며, U는 그 SD를 실행하는 프로그램입니다. 따라서 U가 기계화되어 인간이 아닌 자동 기계로 실행된다면, 그 기계는 그야말로 완전한 프로그램 내장식 컴퓨터인 셈입니다.