The section of the Fount of All Truth (Wikipedia) to you refer to doesn't seem to say that PDF is in fact Turing-complete. In fact it makes it sound like PDF is the result of running a PS document to completion and then taking a "screenshot" of the result. ("Screenshot" as in a snapshot of all the rendered primitives, curves, text, etc.)