55

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.

9
  • 39
    Whether or not something is Turing Complete is not a debate, it's provable. To the people voting to close this as too broad: How is this question any less valid than stackoverflow.com/q/2497146/1766230 which garnered some wonderful answers that were hardly "too long for this format"? Ultimately the answer is a definitive Yes/No with some evidence -- perfect for StackOverflow IMO.
    – Luke
    Jun 8, 2015 at 21:21
  • 4
    I modified the text of the question to try to help, but the correct parsing of that English = "provide an example illustrating how it is Turing Complete, OR provide an example illustrating how it is not Turing Complete." If someone finds a way to both prove and disprove whether a language is Turing Complete, I will award them a medal.
    – Luke
    Jun 8, 2015 at 21:43
  • 7
    The only comment from someone who voted to close showed a misunderstanding of the underlying question -- both "Turing Complete" (not something debatable) and "HTML" (as something distinct from CSS -- referenced in the so-called "duplicate question"). Please allow the community to learn from intelligent answers to thoughtful questions, and vote to reopen this question.
    – Luke
    Jun 9, 2015 at 19:26
  • 4
    @holdenweb The responses to the similar question "Is CSS Turing Complete" were rather short. I suspect that the counter-examples to this question will be about the same size. Why does the asker of the question have the burden of proving that all answers will be short? Why not let the community provide some answers first? Then only if the answers become overly-long, flag the question?
    – Luke
    Jun 10, 2015 at 20:13
  • 12
    Thank you for the question. I definitely would like to see it reopened. Jesus, SO community is often so deplorable. "Hurr, durr, what you are asking doesn't make any sense. I am so good, I know so much, I am part of elite, I reason only in formal logic, I don't use natural languages to communicate, I won't even mentioned what's wrong with the question in my perfect, enlightened opinion". Pathetic. Take this @JK. for example... Dear Lord...
    – user3927220
    Mar 27, 2017 at 11:07

3 Answers 3

41

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.

12
  • 12
    While I expect that "No" is correct, would you elaborate on why HTML is not formally a "machine", and why that's a requirement for Turing Completeness? Couldn't HTML be considered "run" when it is parsed by a browser, just as a JavaScript file is?
    – Luke
    Jun 8, 2015 at 21:53
  • 10
    For starters, HTML hasn't any means of making a "decision", like if ... then ... else. It also has no loops, no variables etc. It is no programming language per se, it is only declarative. Jun 8, 2015 at 23:58
  • 3
    This is not accurate. You can make html into a state machine where each state is represented by an iframe.
    – Travis J
    Jun 10, 2015 at 22:02
  • 10
    @TravisJ Sure, I can represent states with IFRAMEs or in many other ways. But to be a machine we have to be able to transition between states. How would that happen?
    – user663031
    Jun 11, 2015 at 3:10
  • 13
    HTML5 with CSS3 is turing complete, as a Rule 110 implementation was written in it
    – mid
    Jan 14, 2018 at 22:03
23

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

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 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.

8
  • 1
    "In computability theory, a system of data-manipulation rules is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine. This means that this system is able to recognize or decide other data-manipulation rule sets." - wiki definition. Your system would also include a human who would do the clicking, so it's not pure HTML. I'm pretty sure when people say that javascript is turing complete, they mean the engine and not the syntax. Jun 24, 2020 at 6:25
  • 3
    @Anthony Yershov Computability theory is more abstract than that. You don't need an interpreter or even a CPU to determine the computational power of such a rule (e.g. a formal grammar). This kind of analysis is all about the syntax, not the implementation of the mechanism for transitioning between states. So I would say it's pure HTML as much as any formal grammar is "pure".
    – bwdm
    Jun 24, 2020 at 14:44
  • 1
    A link doesn't perform any logical calculation on its own, so I would argue that it couldn't be used to represent state transfer. Jun 26, 2020 at 17:06
  • 3
    The hyperlinks not only represent states transitions, they also work. You can test it yourself.
    – bwdm
    Jun 26, 2020 at 17:32
  • 3
    @AnthonyYershov In your quote "a system of data-manipulation rules" goes against what you are trying to argue. 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.
    – Not_Here
    Nov 20, 2020 at 10:36
1

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.

2
  • 2
    CSS does all the work though.
    – bwdm
    Jan 24 at 21:10
  • Fair point. Still: all HTML documents can contain CSS without limitations; so, the problem of HTML Turing-completeness reduces to CSS Turing-completeness.
    – xeger
    Feb 18 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.