Okay, SO

This post is gonna take place in the mathy, theoretical realm of computer science. It's gonna be all about Turing machines, and I'll tell you what those are. Know that your computer is equivalent to (can compute exactly the same things as, no more no less) than a Turing machine. More or less. We'll get to that.

Imagine a machine with an infinitely long paper tape, like a long spool of receipt paper that's rewritable like a dry erase board*, with a head that can read, write, and erase what's on the tape. We call this a Turing machine, after Alan Turing**, who largely invented and formalized computer science.

One of Turing's big contributions to computing, other than using it to kill Nazis***, was this notion of a Turing machine, which he used to help reason and think about what numbers could actually be computed.

It sounds silly to wonder if any given number can be computed. After all, couldn't you just start at zero and count up until you reached whatever number you liked? Sure, you can, but as we'll see, the hard part is knowing when you've got the right number. Think about how you'd compute a proof that one equals two.

A Turing machine is a very simple thing to program, since it only exists in human heads, and occasionally in textbooks and chalkboards. You'll see physical models of Turing machines sometimes, but, well, call me when one has an actual infinite tape. Every step, the machine will:

- Look at the symbol under the head

- Based on this, move the head any number of places left or right and write any symbols you like along the way.

- Then, read the symbol under the head.

I'm going to try to stay away from computery words like "state", but look at the attached picture real quick. See how it's a collection of circles (states) connected with arrows (state transitions)? Basically, the machine starts in one of the states. Let's say A. This diagram says that if, while in state A, it reads a 0 from the tape, it'll write an R and go to state B. If it reads a 1, it'll write an L and go to state C. Simple, right?

Notice that one of those states is H, and it's circled twice. That's called a "halt state", and it's special. Often, we want a Turing machine to answer some problem, such as "does my tape have the same number of 1s as 0s****." or otherwise signal that it completed its task successfully, such as "I added these two numbers" or "I computed the result you wanted".

Another of Alan Turing's big contributions was formalizing the notion of "algorithm". Last computer word, I promise. An algorithm, in this sense, is a formal series of steps guaranteed to give you some result. You might know an algorithm for baking a cake or doing long division. For example, the a and b machine above might run this algorithm:

State W (start here): if there's an a under the head, write * and go to state X. if there's a b, write * and go to state Y. if *, move right. If there's a blank under the head, halt and accept.

State X: move right. if there's a b under the head, write * and go to state Z. otherwise, go to state X. if there's a blank, signal a fail, perhaps by running forever.

State Y: move right. if there's an a under the head, write * and go to state Z. otherwise, go to state X. if there's a blank, signal a fail, perhaps by running forever.

State Z: move left. if there's a * under the head, move right and go to state W. Otherwise, go to state Z.

Okay, there's a lot going on here, but if you saw the machine in action, you'd figure it out fairly quickly. There's probably a bug in there, but the idea is simple:

- when you see an a or b, mark it off and go to the right until you find the other. if you find it, mark that off and move left back to where you started, then move one right and start over. If you reach the end of the input while looking for a matching a or b (states X and Y), you didn't find one ("reject the string"). If you reach the end of the input after having marked off a matching pair, you've marked them all off and you "accept the string", as they say.

Consider this simple example, where the ^ represents the tape head and the state that got the head where it is in parenthesis. The intermediate moving states are omitted for brevity.

A A A B B

^ (W -> X)

* A A B B

^ (X -> Z)

(Z -> W in here somewhere)

* A A * B

^ (W -> X)

* * A * B

^ (X -> Z)

* * A * *

^ (Z -> W -> X)

* * * * *

^ (X -> fail)

Oop! Looks like that string wasn't matched. There's other ways we could have done this*****, but I hope this makes the point. These machines represent a computation that can be done, a formal mathematical process.

And as it turns out, not everything can be computed! And not just in some touchy-feely "you'll never teach a machine to love" way. The big one Turing talked about is called the "halting problem", which is simply:

Create an algorithm to determine whether a given machine with a given input will ever halt.

This sounds simple, and it is, but this is impossible. You can certainly try (say, with a machine that runs the given machine in side, and seeing if it halts), and you can write programs that get close, but it's impossible to know for sure. How do I know this? Why, we can prove it.

Imagine that I was just lying to you, and I have a Turing machine, we'll call it T, that can determine whether a given machine G halts for a given input I. Then, imagine I modify T so that if G halts on I, T runs forever and halts otherwise.

That is, if I give the modified T our example machine and input up there, T will halt because our example machine does not halt for the input AAABB.

So, what happens if you feed this modified version of T into itself? Well, if it halts, it runs forever, and if it runs forever, it halts. This is clearly impossible, a logical contradction, and therefore T cannot exist.

You'll notice that if you have a machine like T that solves the halting problem, you can use it to determine if any other Turing machine will complete, and therefore, compute anything you like. Shame it doesn't exist.

"What's the use?" You might ask? Well, it turns out a lot of problems are equivalent to the halting problem. In a practical sense, it means you can't, in general, determine whether a given computer program will reach a certain state. That is, you can't write a program that, given another program as input, determines whether it'll crash (and can guarantee it- there are programs that try to figure this out, with varying degrees of success)

You'll hear people, such as myself, talk about being "Turing complete". If something is "Turing complete", it means that it is as powerful as a Turing machine and can compute everything a Turing machine can. You'll hear people talk about surprising things that are Turing complete, like Magic the Gathering******, Baba is You, Microsoft Excel, and Conway's Game of Life.

Anyways, this turned out to be way longer than I thought, and I hope it helped someone!

* We can theorize about Turing machines with multiple tapes, non-rewritable tapes, tapes that are only infinite in one direction, and the like, but ultimately, it doesn't make the machines more powerful, only faster or slower. They can be useful tools for helping us construct Turing machines, though.

** He's really cool, look him up or watch that Benedict Cumberbatch movie, but fair warning: his story does not end well, since he was a gay man in 1954 Britain.

*** hell yeah

**** I'm using ones and zeroes right now, but the symbols can be anything, and there can be as many as you want. Letters, #$%^&*, digits 0-9, you name it. You also usually have a blank space, which is what the tape is filled with at the start.

***** for example, if you have a two tape machine (or want to emulate one, since you can have a one-tape machine pretend to have two tapes), have one tape with your string and the other increment a counter when it sees an a and decrement the counter when it sees a b. if the counter is zero at the end of the string, you're good.

****** Google it- since the battlefield can have an infinite number of tokens on it, your tape is creature tokens and their types are the symbols.

Sen. Samantha Bananathon@BestGirlGrace@social.illegalpornography.comone of these days, I'll write up a thing on the halting problem so everyone can laugh with me