01: Universal Redirect Locomotive
Did you ever lie awake at night wondering if the HTTP spec was Turing-complete? Just me? Damn.
First, a bit of background. The hypertext transfer protocol is the web’s standard way of piping bits around the globe. It’s the agreement between servers and clients for how to send, retrieve, modify, and delete data (and properties of that data) over the web. For the purpose of this exercise, we can ignore everything in the spec but the URL and the response headers. Those are all you need to build a computer.
The Universal Redirect Locomotive is a stateless web application that serves Turing Machines. It relies on two premises: first, a Turing Machine (its program, input, and current state) can be represented in a URL; and second, web clients will follow a redirect response sent by the server. All the server needs to do is read the machine’s representation from the request and iterate the machine one step. The server is only concerned with the transition that corresponds with the current state and the character currently under the read-write head. Then it sends the modified representation back to the client as a redirect.
If the web client follows the redirect, the changing representations bouncing back and forth are what perform the computation. Yes, you heard that right: the program executes by following a redirect loop to its bitter end. The process continues until the machine halts by either reaching a state where no transition exists (the current state and given input have no matches in the transition list) or by running the read-write head off the end of the tape.
Example 1
This is a simple program that tests whether a string is a sequence of A’s terminated by a B. (If the machine halts in state z, the string is a match.)
http://localhost/q(AA)>q;q(BB)>z/q/AAAAAAAB
The state transitions are the semicolon-separated list in the first portion of the request path. The transition specifier q(BB)>z represents the transition from an initial state q upon encountering a B. The transition itself replaces the encountered character with B, moves the position of the head one cell to the right on the input tape, and moves the machine into state z.
Example 2
Here’s a more complex machine that corrects a loop that has too many O’s.
http://localhost/a(ll)>a;a(oo)>b;b(oo)>c;c(oo)>d;c(pp)>z;d(oo)>d;d(p)<e;e(op)<f;f(oo)<f;f(ll)>a/a/loooop
And here’s a peek at part of its execution. (Client request lines start with ‘>’ and server response lines start with ‘<’.)
> GET /a(ll)>a;a(oo)>b;c(oo)>d;c(pp)>z;b(oo)>c;e(op)<f;d(oo)>d;d(p)<e;f(oo)<f;f(ll)>a/f/|l|oop HTTP/1.1
< HTTP/1.1 302 Found
< Location: http://localhost:8080/a(ll)>a;a(oo)>b;c(oo)>d;c(pp)>z;b(oo)>c;e(op)<f;d(oo)>d;d(p)<e;f(oo)<f;f(ll)>a/a/l|o|op
> GET /a(ll)>a;a(oo)>b;c(oo)>d;c(pp)>z;b(oo)>c;e(op)<f;d(oo)>d;d(p)<e;f(oo)<f;f(ll)>a/a/l|o|op HTTP/1.1
< HTTP/1.1 302 Found
< Location: http://localhost:8080/a(ll)>a;a(oo)>b;c(oo)>d;c(pp)>z;b(oo)>c;e(op)<f;d(oo)>d;d(p)<e;f(oo)<f;f(ll)>a/b/lo|o|p
> GET /a(ll)>a;a(oo)>b;c(oo)>d;c(pp)>z;b(oo)>c;e(op)<f;d(oo)>d;d(p)<e;f(oo)<f;f(ll)>a/b/lo|o|p HTTP/1.1
< HTTP/1.1 302 Found
< Location: http://localhost:8080/a(ll)>a;a(oo)>b;c(oo)>d;c(pp)>z;b(oo)>c;e(op)<f;d(oo)>d;d(p)<e;f(oo)<f;f(ll)>a/c/loo|p|
> GET /a(ll)>a;a(oo)>b;c(oo)>d;c(pp)>z;b(oo)>c;e(op)<f;d(oo)>d;d(p)<e;f(oo)<f;f(ll)>a/c/loo|p| HTTP/1.1
< HTTP/1.1 200 OK
Coda
Thankfully, we can all sleep well at night knowing that any computable program can be executed by following endless redirects from a sufficiently long URL. For those of you who care about such things, the Universal Redirect Engine is written in Python using the Tornado web server, and brave souls can view the source code at the 1010 repository on GitHub.
