A function is computable if, over the domain of natural numbers (0,1,2,3...) there is a finite sequence of instructions (or an algorithm) that states exactly how to list the value of f(x) at f(0), and, for any n at f(n+1). Just like most math, this follows the simple formula of question to answer; however, we’re about to turn ordinary math on its head. When Alan Turing looked at the definition of computable, he decided to run the statement in the form of answer to question, writing that “a function is computable if its decimal can be written by a machine.” This, to me, lends the question “what is a computer?” When I first addressed this idea, I looked up from my laptop at all of the other ones in the English room, and the answer seemed obvious. Not to Turing, especially considering he lived in a time without what we generally considered computers. In Turing’s world, a computer is merely a human with pencil, paper, and time.  

A Turing Machine, according to “On Computable Numbers,” is actually a Logical Computing Machine (LCM). There are only a few requirements to be an LCM:

1. Be a system, theoretically a box (this box can be as simple as a typewriter or as complex as a human)

2. Be able to read and write:

   1. a finite alphabet of symbols

   2. from a finite (but unbounded) length of tape

3. Be able to change m-configurations (state of mind)

An LCM additionally assumes two things: discreteness of time and state of mind. Essentially, the machine can only be in one state at a time, both in terms of internal state and position along the type; a Turing Machine demonstrates the relationship between symbols in space and sequence of events in time. Here’s what a Turing Machine can do, in a simple list.

1. Alter its m-configuration and remember symbols

2. If the space is blank, write symbols

3. Erase symbols

4. Can shift the tape left or right

5. Look at one cell at a time

Each step in this relationship is determined by an instruction table that lists all of the possible internal states, all symbols, and (for every combination) what the machine will do. Remember, this function is limited by the list above; a machine can write a symbol, erase a symbol, and move the tape in either direction. When following the set of instructions, a Turing Machine never makes a mistake, as it can only follow the protocol outlined in the table of values. There is no thought, even when the machine is human, and all a Turing Machine needs is two internal states to function, so in that way, Turing Machines might be considered of greater intelligence than ninth graders. Additionally, the behavioral complexity is the same no matter the complexity of the m-configurations or symbols. Of course, while all of this information on different machines is fascinating, the paper culminated in the discussion of a Universal Turing Machine, a single machine to compute any computable sequence.

The Universal Turing Machine, given its function, is much easier to think about in terms of theory, as the number of independent tapes and systems for each letter is difficult to picture. The theory, however, is relatively simple: when faced with an encoded message from another machine, the machine executes the sequence to reveal the original message. As my notes excitedly state in the margins of the paper, this idea is fancy terminology for decoding. 

Now that we know how Turing Machines function, it is time to decode and create our own. Think of it as a game of Jeopardy, but with numbers. Generally, a Deterministic Turing Machine contains the same functions as a general Turing Machine, but they also contain additional properties.

Consider this Turing Machine:

Now that we understand how the game is played, let's design our own halting function. The easiest way to do that is to have a pattern of crossing off 0s and 1s that will cross all desired numbers off regardless of the number of cells.

As we can see, this is clearly a decidable and recognizable function, so the action of the machine on a string is redundant. 

There is one other crucial point to discuss in terms of Turing Machines, and that is Alan Turing himself. There’s one line that’s repeated throughout the recent movie about Turing: “sometimes it is the people who no one imagines anything of who do the things that no one can imagine." I’ve thought about this line more than I should, as I’ve thought about Turing and his story. Despite his incredible advancements of math and his work cracking Enigma during World War II, he was convincted of ‘indecency’ due to his homosexuality and forced to undergo conversion treatments until he commits suicide. For this arbitrary reason, no one would expect Turing to have done extraordinary things, and yet it was him who led the team of people who cracked the world’s most unsolvable problem. I need to understand Turing’s work because he needs to be recognized and remembered for what he’s done. He went through too much for me to separate the man from the machine, and watching this movie turned a spark of curiosity into a flame that burned at my insides until I understood. Turing created the field of computer science, and yet few people know who he is, what he did, and the number of lives he saved. 

If there’s one thing I’ve learned from this move, it’s that I can’t ignore the stories of those who create the math. Math works like history in that it allows us to redeem ourselves by keeping people like Turing’s legacy alive, to try to fix the problems and the crimes we have done upon these people. We still study Turing’s machines, and by doing so I feel as if we’re working to fix the mistakes that have been made in the past. I want to know why math remembers certain people’s stories. I can’t think about braiding without thinking about Edward Frenkel leaving Soviet Russia to study math somewhere he isn’t denied the opportunity due to his Jewish last name. I can’t look at my computer without think about the ‘correctional’ treatments that drove Alan Turing to suicide.

Why do I study math? Is saying that I love it enough anymore?