Other things like JavaScript and Flash can be embedded, but they are extras on top of the document.
I presume the extensions to embed javascript are Turing complete, and IMO do not belong in a PDF file.
I've also heard that some of the embedded font formats have features that are Turing complete, but I don't know the details on that.
If there is a way to implement a Turing machine in PDF, outside of the fonts and javascript, I'd love to see the details. (I know somebody managed it with just the macro expansion bit of TeX.)
Very roughly speaking (this is a semantic debate where everyone is wrong from someone else's perspective), a PDF file is a restricted subset of Postscript, with added indexes so one can render pages in the middle without having to process the code from the beginning.
The hardship in generating PDFs from scratch is getting those indexes right. It's far easier to convert a Postscript file using standard tools.