News for hackers. Stuff that matters.
Re:Borb – A Python library to read, write, and edit PDF files by hyperpallium2 on Saturday September 18, 2021 @09:17AM (#28576013)
PDF uses postscript, which is Turing equivalent. It's a document format with the halting problem.
Re:Borb – A Python library to read, write, and edit PDF files by mkl on Saturday September 18, 2021 @11:26AM (#28576966)
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/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.

Re:Borb – A Python library to read, write, and edit PDF files by dunham on Saturday September 18, 2021 @11:25AM (#28576963)
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.)

Re:Borb – A Python library to read, write, and edit PDF files by maxerickson on Saturday September 18, 2021 @10:44AM (#28576649)
Postscript files are often rendered into PDF, but PDF doesn't use postscript.
Re:Borb – A Python library to read, write, and edit PDF files by Syzygies on Saturday September 18, 2021 @04:17PM (#28578948)
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.

Re:Borb – A Python library to read, write, and edit PDF files by maxerickson on Sunday September 19, 2021 @03:09PM (#28587004)
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.
Re:Borb – A Python library to read, write, and edit PDF files by kaba0 on Sunday September 19, 2021 @04:07AM (#28582595)
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.
Re:Borb – A Python library to read, write, and edit PDF files by einpoklum on Saturday September 18, 2021 @10:16AM (#28576448)
That is not a realistic concern for GP. The scanned exams won't even involve any Postscript.
Re:Borb – A Python library to read, write, and edit PDF files by Syzygies on Saturday September 18, 2021 @04:06PM (#28578866)
I do insert the score radio buttons using the "pdfmark" mechanism via Postscript.
Re:Borb – A Python library to read, write, and edit PDF files by selfhoster11 on Saturday September 18, 2021 @04:14PM (#28578927)
HTML uses JavaScript which is also Turing complete. Lack of the halting problem is nice, but having it is not a show stopper.