Is HTML Turing Complete?

Question

By itself (without CSS or JS), HTML (5 or otherwise) cannot possibly be Turing-complete because it is not a machine. Asking whether it is or not is essentially equivalent to asking whether an apple or an orange is Turing complete, or to take a more relevant example, a book.

HTML is not something that "runs". It is a representation. It is a format. It is an information encoding. Not being a machine, it cannot compute anything on its own, at the level of Turing completeness or any other level.

It seems clear to me that states and transitions can be represented in HTML with pages and hyperlinks, respectively. With this, one can implement deterministic finite automata where clicking links transitions between states. For example, I implemented a few simple DFA which are accessible here.

DFA are much simpler that the Turing Machine though. To implement something closer to a TM, an additional mechanism involving reading and writing to memory would be necessary, besides the basic states/transitions functionality. However, HTML does not seem to have this kind of feature. So I would say HTML is not Turing-complete, but is able to simulate DFA.

Edit: I was reminded of the video On The Turing Completeness of PowerPoint when writing this answer.

Edit: complementing this answer with the DFA definition and clarification.

Definition

From https://en.wikipedia.org/wiki/Deterministic_finite_automaton#Formal_definition

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string.

A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q0, F), consisting of

• a finite set of states Q
• a finite set of input symbols called the alphabet Σ
• a transition function δ : Q × Σ → Q
• an initial or start state q0
• a set of accept states F

The following example is of a DFA M, with a binary alphabet, which requires that the input contains an even number of 0s.

M = (Q, Σ, δ, q0, F) where

• Q = {S1, S2}
• Σ = {0, 1}
• q0 = S1
• F = {S1} and
• δ is defined by the following state transition table:

	0	0
s1	s2	s1
s2	s1	s2

State diagram for M:

The state S1 represents that there has been an even number of 0s in the input so far, while S2 signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not. If the input did contain an even number of 0s, M will finish in state S1, an accepting state, so the input string will be accepted.

HTML implementation

The DFA M exemplified above plus a few of the most basic DFA were implemented in Markdown and converted/hosted as HTML pages by Github, accessible here.

Following the definition of M, its HTML implementation is detailed as follows.

• The set of states Q contains the pages s1.html and s2.html, and also the acceptance page acc.html and the rejection page rej.html. These two additional states are a "user-friendly" way to communicate the acceptance of a word and don't affect the semantics of the DFA.
• The set of symbols Σ is defined as the symbols 0 and 1. The empty string symbol ε was also included to denote the end of the input, leading to either acc.html or rej.html state.
• The initial state q0 is s1.html.
• The set of accept states is {acc.html}.
• The set of transitions is defined by hyperlinks such that page s1.html contains a link with text "0" leading to s2.html, a link with text "1" leading to s1.html, and a link with text "ε" leading to acc.html. Each page is analogous according to the following transition table. Obs: acc.html and rej.html don't contain links.

	0	1	ε
s1.html	s2.html	s1.html	acc.html
s2.html	s1.html	s2.html	rej.html

Questions

• In what ways are those HTML pages "machines"? Don't these machines include the browser and the person who clicks the links? In what way does a link perform computation?

DFA is an abstract machine, i.e. a mathematical object. By the definition shown above, it is a tuple that defines transition rules between states according to a set of symbols. A real-world implementation of these rules (i.e. who keeps track of the current state, looks up the transition table and updates the current state accordingly) is then outside the scope of the definition. And for that matter, a Turing machine is a similar tuple with a few more elements to it.

As described above, the HTML implementation represents the DFA M in full: every state and every transition is represented by a page and a link respectively. Browsers, clicks and CPUs are then irrelevant in the context of the DFA.

In other words, as written by @Not_Here in the comments:

Rules don't innately implement themselves, they're just rules an implementation should follow. Consider it this way: Turing machines aren't actual machines, Turing didn't build machines. They're purely mathematical objects, they're tuples of sets (state, symbols) and a transition function between states. Turing machines are purely mathematical objects, they're sets of instructions for how to implement a computation, and so is this example in HTML.

The Wikipedia article on abstract machines:

An abstract machine, also called an abstract computer, is a theoretical computer used for defining a model of computation. Abstraction of computing processes is used in both the computer science and computer engineering disciplines and usually assumes a discrete time paradigm.

In the theory of computation, abstract machines are often used in thought experiments regarding computability or to analyze the complexity of algorithms (see computational complexity theory). A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former into the latter. The best-known example is the Turing machine.