Turing Machine and REST

    Dhaivat Pandya
    Dhaivat Pandya
    Share

    We see it all the time. “RESTful” this, “REST” protocol that, etc. However, a lot of us don’t really understand exactly what it means. We’ll fix exactly that gap in this article!

    State

    In computer science (and mathematics, to some extent), there is a concept of state. A certain system can be in state A or it can be in state B or it can be a bunch of other states (usually, a finite list of states). As an example, let us say that you write a program which turns the screen red if the temperature is more than 80 degreees farenheit or turns it blue if the temperature is less than 80 degrees farenheit. We can call the first state (temp > 80 degrees) state “A” and the second state (temp < 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C. That is the general idea of state. Here’s the definition given by the all-knowing Wikipedia: “In computer science and automata theory, the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given point in time, which is used by the circuit or program.” In short, it is a sort of “combination” of all the information that the program takes into account. Now, we’re going to make a leap into something that’s considered largely theoretical and useless and then somehow connect to the very practical world of REST.

    Turing machines

    There was this man named Alan Turing, and he was quite a smart mathematician with an interest in the workings of computers. He conceived an imaginary computer (which, as we will see, is actually impossible to actually build) which he used to reason about things that happen in real computers. The computer consists of a tape of infinite length, with a head through which the tape passes. The tape has “cells”, to which information can be written (numbers, colors, etc.) The tape moves through this machine, left or right, one cell at a time. The machine scans in whatever is already on the tape and, depending on what state it is in, it writes something back onto the tape then, subsequently, changes its state. You may want to read that definition again for it to sink in completely. The essence of the idea is that it makes operations on memory based on state and states changes according to operations on memory. This seems like a fairly useless theoretical fantasy (although, there is absolutely nothing wrong with that, read A Mathematician’s Apology
    if you’re wondering why people care to take an interest in theoretical stuff). However, it is quite possibly the most fundamental concept of computer science. Using the Turing Machine, computer scientists are able to reason about any algorithm that can be run on a computer. In fact, the Turing machine has led to many advances in computer science. So, the Turing Machine shows us that today (note: I’m not considering graph reduction processors), literally everything in computer science is based off the idea of state.

    The Network

    Then came along the concept of the internet. This is a place where packets can go haywire and are resent until they reach their destination. In general, there is never a complete transmission of full data. Clients come in quickly and leave twice as fast. As such, holding onto client state doesn’t make much sense when working on a network system. Also, in general, holding too much state in a system has been a cause for major pain (which also leads to funcitonal programming languages, which do not allow for the holding of state in a large portion of your code). Now, people needed a network protocol for the internet which was simple, fast and handled management of state well in an extremely dynamic environment. That protocol was HTTP, and the theory that grew out of the work on HTTP was labelled REST.

    REST

    REST stands for: REpresentational State Transfer. It is a system built around the “client-server” concept that networks are built on top of (well, ther are also peer to peer type networks, but, client-sever is arguably the simplest and most tested architecture). The name itself is slightly misleading, since the server is completely state-free! There are a few constraints that all systems that claim to be “RESTful” must follow. First of all, it must be a client-server system. This constraint has been modified in the past, but in the formal definition (and, for the theory of REST to work properly), we have servers to which clients can connect. The server is fully stateless. This means that for each client request to the server, no state is reserved on the server. For example, if a client (using HTTP), requests the index page and subsequently requests the /user/home page, the two requests are completely independent of each other. The client holds all of the state of the system (hence, we have the back button). Responses from the server must be cacheable, which means that there must be a system on the server which identifies respones as cacheable or not, so that clients (e.g. web browsers) can take advantage of the cache. Finally, we must have a simple, clean, and uniform interface. If you have had some experience with how HTTP works, the request forms are very simple. They are largely verbs and nouns with a very easy to parse and human-readable format. SOAP is another form of a network protocol which absolutely obliterates this requirement and, therefore, is often very difficult to work with. Now, what do all of these properties, when taking together, entail?

    Implications of REST

    They let us build systems that are cleanly seperated, scalable, and debugged easily. Let us consider the restriction of statelessness on the server first, it may well be the most important (and, also, the most often violated by so-called RESTful architectures) bit. As previously mentioned, in a client-server architecture the clients are very nimble; they fire requests and suddenly kill all communication. In this kind of a situation, it is much cleaner to not save state about the client on the server. This lets us reason about HTTP servers very easily; each client request may be treated as if it is a completely new client, and it wouldn’t make a penny of a difference. Secondly, cacheable responses mean that the clients are able to get data much faster, because often times, the data can be retrieved from the client’s memory. This immediately increases client performance and, in some systems, server scalability. The uniform interface may just be the most important. Having worked with SOAP, I can tell you that HTTP’s simple format is a blessing when trying to debug server code and the same applies to other RESTful systems.

    Designing a RESTful System

    Let’s say we need to write a server that returns stock quotes, as well as retaining a list of stock quotes to monitor (and, the user can either add to or clear the list). This is an excellent case for a RESTful system, because it is inherently independent of identity of client. Therefore, the server need not hold any state about the client. We first start by defining how the protocol language will work (a bit like the GET and POST verbs of HTTP): GETQUOTE ticker – gives the price for a particular stock ADDTICKER ticker – adds the given stock to the list GETLIST – gets a comma seperated list of stocks in the list That’s a fairly simple protocol, and, doesn’t hold any state on the server. Now, as for caching, we may say that we update the prices every hour, so caches more than one hour old may be thrown away. And, that’s all there is to it! Of course, we still have to implement this, but, the general idea of the system is quite simple and clean!

    Conclusion

    Hopefully, this article gave you a solid understanding of REST. Also, I hope that you will now be able to call out people who throw around the term “RESTful” too much – I can tell you, there’s a lot of them! Please ask any questions in the comments, or tweet them out to me at @dhaivatpoincare :)

    Frequently Asked Questions about Turing Machine and CSS

    What is a Turing Machine and how does it relate to CSS?

    A Turing Machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. It’s a fundamental concept in computer science and forms the basis of modern computers. CSS, or Cascading Style Sheets, is a style sheet language used for describing the look and formatting of a document written in HTML. The relation between a Turing Machine and CSS is that some argue CSS is Turing complete, meaning it can solve any problem that a Turing machine can, given enough time and resources.

    Is CSS really Turing complete?

    The concept of Turing completeness is a subject of debate when it comes to CSS. Some argue that CSS is Turing complete when combined with HTML markup because it can simulate Rule 110, a cellular automaton known to be Turing complete. However, others argue that CSS lacks certain features, such as the ability to store arbitrary amounts of data, which are necessary for a system to be truly Turing complete.

    What is Rule 110 and how does it relate to CSS?

    Rule 110 is a cellular automaton rule introduced by mathematician John Horton Conway. It’s known for its surprisingly complex behavior and is proven to be Turing complete. The relation to CSS is that some have demonstrated that CSS, when combined with HTML markup, can simulate Rule 110, which is one of the arguments for CSS being Turing complete.

    Why is there a debate about CSS being Turing complete?

    The debate arises from the definition of Turing completeness. Some argue that because CSS can simulate Rule 110, it is Turing complete. Others argue that CSS lacks certain features, such as the ability to store arbitrary amounts of data, which are necessary for a system to be truly Turing complete. The debate is largely academic, as CSS is primarily used for styling web pages, not for general computation.

    What are the implications if CSS is Turing complete?

    If CSS is indeed Turing complete, it would mean that it’s theoretically capable of performing any computation, given enough time and resources. However, in practice, CSS is not used for general computation but for styling web pages. The debate about CSS’s Turing completeness is more of an interesting theoretical discussion rather than something that has practical implications for web development.

    Can CSS be used for general computation?

    While CSS has been shown to be capable of simulating Rule 110, a Turing complete cellular automaton, it’s not practical to use CSS for general computation. CSS is a style sheet language designed for describing the look and formatting of a document written in HTML. It lacks features that are common in programming languages, such as variables and functions.

    What does it mean for a system to be Turing complete?

    A system is said to be Turing complete if it can simulate a Turing machine. In other words, it can perform any computation that can be described by a Turing machine, given enough time and resources. This is a fundamental concept in computer science and forms the basis of modern computers.

    How does HTML factor into the debate about CSS being Turing complete?

    HTML, or HyperText Markup Language, is the standard markup language for documents designed to be displayed in a web browser. Some argue that CSS is Turing complete when combined with HTML markup because it can simulate Rule 110, a cellular automaton known to be Turing complete.

    What is the practical significance of a system being Turing complete?

    The practical significance of a system being Turing complete is that it can perform any computation, given enough time and resources. This is a fundamental concept in computer science and forms the basis of modern computers. However, in the context of CSS and web development, the debate about CSS’s Turing completeness is more of an interesting theoretical discussion rather than something that has practical implications.

    Are there other style sheet languages that are Turing complete?

    CSS is the most widely used style sheet language, and the debate about its Turing completeness is unique to it. Other style sheet languages, such as XSLT, are Turing complete, but they are designed with more computational features and are used for different purposes than CSS.