4

The following questions are rather theoretical/academical in nature.

According to Wikipedia

a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine.

It is said that TeX is Turing-complete.

I think about the implications of these statements.

There are several TeX-engines—e.g., Knuth's TeX, ε-TeX, pdfTeX, XeTeX, LuaTeX, uTeX, upTeX.

Ouestion 1:

Are these TeX-engines Turing-complete?

Ouestion 2:

Are these TeX-engines Turing-machines?

If so:

Question 3:

Is it possible to simulate, e.g., a LuaTeX engine (with unicode as internal character encoding scheme) on an 8-bit Knuth TeX engine (with ASCII as internal character encoding scheme)?

"Being a Turing-machine and not something whereof a Turing-machine is a strict subset" and "Being Turing-complete" are different properties. If TeX-engines are Turing-complete without being just Turing-machines themselves, you cannot conclude that different TeX-engines can simulate one another.

Question 4:

Is Turing-machinery a strict subset of these TeX-engines?

Do TeX-engines have components which do not belong to the concept of a Turing-machine?

Improve this question
3
  • 1
    Turing completeness says nothing about (for example) internal data representations or expansion or .... For example, we can read tokens one at a time in an 8-bit engine to reconstruct Unicode codepoints, but that won't let us do expandable assignments (cf. \directlua).
    – Joseph Wright ♦
    Commented Jan 6, 2021 at 21:34
  • A Turing machine is a purely mathematical object to define computability. Depending on ones viewpoint, a TeX engine can be anything between an abstract concept and a physical object. In none of these interpretations, the question whether one is a strict subset of the other makes sense. One can ask whether one model of computability can simulate some other (which is the case with Turing machines and TeX engines with unbounded memory), or what the space/time complexity of this simulation is.
    – gernot
    Commented Jan 6, 2021 at 23:30
  • Since TeX renders text as a linked list of character structures, changing from char to wchar would be relatively trivial.
    – John Kormylo
    Commented Jan 7, 2021 at 16:23

4 Answers 4

Reset to default
9

Question 1: Yes, if you assume that these engines have access to unbounded memory and time (not infinite, but expandable whenever more memory/time is needed), as one usually assumes when saying that computers are Turing-complete.

Question 2: No. Turing-machines are a mathematical model of computation, like register machines, lambda calculus and many others. TeX engines, real computers etc are realizations of a mixtures of different models.

Question 3: Yes, if you answer Question 1 with yes. Every Turing-complete formalism can simulate any other modulo some input/output transformations (otherwise it wouldn't be Turing-complete). This doesn't say anything about the practicability. E.g., you can use the TeX engine (with unbounded memory/time) to simulate an x86 architecture, which runs Linux, which runs XeTeX. However, I wouldn't want to delay my breakfast while waiting for the result of typesetting Hello, world!\bye.

Improve this answer
2
4

Is it possible? Theoretically, but while TeX is Turing-complete, it is restricted in its memory capacity and you would probably run out of capacity before you got there. I'm guessing that one would need to re-implement TeX in TeX macros as part of the project as well as writing a full Lua interpreter also in TeX macros. The limitations of the TeX macro language are such that you would probably want to write a compiler that compiles some higher-level language such as C to TeX macros to do this. If you wrote this compiler in C, it could bootstrap itself to then run as TeX macros itself. But again, memory capacity is and always will be an issue.

Improve this answer
4

A Turing-complete language is capable of computing all computible functions on integers.

It would be possible to represent a Unicode system in some format that the older system could compute, convert the inputs to their compatible representation, and then produce the representation of the output, all on on an older TeX engine, given sufficient time and memory. In fact, a Turing-compatible TeX engine could simulate the entire computer running LuaTeX.

This does not necessarily imply that a legacy TeX engine could read UTF-8 input and produce a Unicode PDF with embedded OpenType fonts. In theory, though, it could be the backend to a system that converts the input and the output of the legacy TeX engine to and from the compatibile representation, respectively.

Improve this answer
2
  • It might be easier to recompile the old system with 32 bit char variables.
    – Joshua
    Commented Jan 7, 2021 at 16:43
  • @Joshua That’s an entirely different question! The original TeX was not written in C, but that’s trivial. PDFTeX already can read UTF-8 input, through an inputenc hack, but not Unicode combining characters that follow the base character. Converting to `32-bit internal characters would not solve that, or any of the many places in legacy TeX that assume there are at most 256 characters in any encoding.
    – Davislor
    Commented Jan 7, 2021 at 18:12
2

Do TeX-engines have components which do not belong to the concept of a Turing-machine?

There is one aspect that is not considered by the Turing machine models: input and output capabilities.

For example, if a particular TeX engine would be limited to .pdf output and did not permit creation of arbitrary files, it would be impossible to make it output .dvi files. It could format them in memory and embed them as text inside PDF, but then you would need a separate step to extract the final output.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .