4 ms·

PDF uses postscript, which is Turing equivalent. It's a document format with the halting problem.

by hyperpallium2 5y ago

einpoklum 5y ago
That is not a realistic concern for GP. The scanned exams won't even involve any Postscript.
- deleted 5y ago
  [deleted]
- Syzygies 5y ago
  I do insert the score radio buttons using the "pdfmark" mechanism via Postscript.
maxerickson 5y ago
Postscript files are often rendered into PDF, but PDF doesn't use postscript.
- Syzygies 5y ago
  See dunham's answer. Anyone who has seen a PDF file in text form would swear they're looking at Postscript. There's a common intersection that's identical. 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.
  - kaba0 5y ago
    The same way as JSON is a subset of JS, it has radically different properties that way, so comparisons to postscript is not really meaningful.
  - maxerickson 5y ago
    That's fair. I was waffling about using stronger language, "pdf isn't postscript", but didn't get there. It would have been more correct.
dunham 5y ago
It's based on postscript, like json is based on javascript. I don't believe there are any control flow (or even general arithmetic?) instructions in the content streams, so I don't see how it could be Turing complete. It's just a sequence of drawing and transformation commands, like SVG. 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.)
- deleted 5y ago
  [deleted]
mkl 5y ago
PDF does not use Postscript, and is not Turing complete. Its drawing model is based on Postscript's (with additions), but its instruction set is focused on drawing, and can't do programming. Here is the instruction set, with equivalent Postscript commands where applicable: https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=651 https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PD.... Most parts of the Postscript language have no PDF equivalent. Other things like JavaScript and Flash can be embedded, but they are extras on top of the document.
selfhoster11 5y ago
HTML uses JavaScript which is also Turing complete. Lack of the halting problem is nice, but having it is not a show stopper.

PDF uses postscript, which is Turing equivalent. It's a document format with the halting problem.

einpoklum 5y ago

That is not a realistic concern for GP. The scanned exams won't even involve any Postscript.

deleted 5y ago
[deleted]
Syzygies 5y ago
I do insert the score radio buttons using the "pdfmark" mechanism via Postscript.

maxerickson 5y ago

Postscript files are often rendered into PDF, but PDF doesn't use postscript.

Syzygies 5y ago
See dunham's answer. Anyone who has seen a PDF file in text form would swear they're looking at Postscript. There's a common intersection that's identical. 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.
- kaba0 5y ago
  The same way as JSON is a subset of JS, it has radically different properties that way, so comparisons to postscript is not really meaningful.
- maxerickson 5y ago
  That's fair. I was waffling about using stronger language, "pdf isn't postscript", but didn't get there. It would have been more correct.

dunham 5y ago

It's based on postscript, like json is based on javascript. I don't believe there are any control flow (or even general arithmetic?) instructions in the content streams, so I don't see how it could be Turing complete. It's just a sequence of drawing and transformation commands, like SVG. 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.)

deleted 5y ago
[deleted]

mkl 5y ago

PDF does not use Postscript, and is not Turing complete. Its drawing model is based on Postscript's (with additions), but its instruction set is focused on drawing, and can't do programming. Here is the instruction set, with equivalent Postscript commands where applicable: https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=651 https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PD.... Most parts of the Postscript language have no PDF equivalent. Other things like JavaScript and Flash can be embedded, but they are extras on top of the document.

selfhoster11 5y ago

HTML uses JavaScript which is also Turing complete. Lack of the halting problem is nice, but having it is not a show stopper.