After reading this question Is CSS Turing complete? -- which received a few thoughtful, succinct answers -- it made me wonder: Is HTML Turing Complete?
Although the short answer is a definitive Yes or No, please also provide a short description or counter-example to prove whether HTML is or is not Turing Complete (obviously it cannot be both). Information on other versions of HTML may be interesting, but the correct answer should answer this for HTML5.
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.
Edit1: I was reminded of the video On The Turing Completeness of PowerPoint when writing this answer.
Edit2: complementing this answer with the DFA definition and clarification.
Edit3: it might be worth mentioning that any machine in the real world is a finite-state machine due to reality's constraint of finite memory. So in a way, DFA can actually do anything that any real machine can do, as far as I know. See: https://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines
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.
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.
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.acc.html or rej.html state.s1.html.acc.html}.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 |
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.
Some have claimed to implement Rule 110, a cellular automaton, using pure HTML and CSS (no JavaScript). You can see a video here, or browse the source of one implementation.
Why is this relevant? It has been proven that Rule 110 is itself Turing complete, meaning that it can simulate any Turing machine. If we then implement Rule 110 using pure HTML, it follows that HTML can simulate any Turing machine via its simulation of that particular cellular automaton.
The critiques of this HTML "proof" focus on the fact that human input is required to drive the operation of the HTML machine. As seen in the video above, the human's input is constrained to a repeating pattern of Tab + Space (because the HTML machine consists of a series of checkboxes). Much as a Turing machine would require a clock signal and motive force to move its read/write head if it were to be implemented as a physical machine, the HTML machine needs energy input from the human -- but no information input, and crucially, no decision making.
In summary: HTML is probably Turing-complete, as proven by construction.
