The recent movie “The Imitation Game” gave [Alan Turing] some well-deserved fame among non-computer types (although the historical accuracy of that movie is poor, at best; there have been several comparisons between the movie and reality). However, for people in the computer industry, Turing was famous for more than just helping to crack Enigma. His theoretical work on computing led to the Turing machine, which is still an important concept for reasoning about computers in a mathematical way. He also laid the foundation for the stored program computer that we take for granted today.
What’s a Turing Machine?
A Turing machine is deceptively simple and, like many mathematical models, highly impractical. Leading off the inpracticalities, the machine includes an infinite paper tape. There is a head that can read and write any symbol to the tape at some position, and the tape can move to the left or the right. Keep in mind that the head can write a symbol over another symbol, so that’s another practical difficulty, although not an insurmountable one. The other issue is that the symbol can be anything: a letter, a number, a jolly wrencher, or a bunch of dots. Again, not impossible, but difficult to do with practical hardware implementations.
Put that aside for a minute, though. The machine also has a current state and a finite table of actions that will dictate the operation of the machine. Each row in the table contains a current state and a current symbol. A row that matches the current state and current symbol will direct the action of the machine. The rest of the row contains a symbol to print on the tape (which could be the same as the current symbol), if the tape should move left or right by one step, and a new state (which could, of course, be the same as the current state).
You might wonder how this constitutes a practical computer. Well, practical might be a bit much, but you can do arbitrary tasks, although sometimes it takes a lot to do even simple tasks. For example, here’s a really simple machine that prints 001 on the tape:
| Current State | Current Symbol | Next Symbol | Move | Next State |
|---|---|---|---|---|
| A | $ANY | 0 | Right | B |
| B | $ANY | 0 | Right | C |
| C | $ANY | 1 | Right | $HALT |
The machine starts in state A and ends at state $HALT. The $ANY keyword matches any symbol. Here’s a more interesting example that inverts a binary number:
| Current State | Current Symbol | Next Symbol | Move | Next State |
|---|---|---|---|---|
| A | 0 | 1 | Right | A |
| A | 1 | 0 | Right | A |
| A | $ANY | $NOCHANGE | $NOCHANGE | $HALT |
In this case, there is only one state. Any 0 becomes a 1 and any 1 becomes a 0. The first symbol that isn’t either a 0 or a 1 stops the operation.
In the Wild
Even though you can’t build a real machine with an infinite tape and all the other impracticalities of a true Turing Machine, it doesn’t stop people like [Mike Davey] from building practical ones that are good enough. You can see a video of this machine below.
Clearly, [Mike’s] machine is practically art. If you are less ambitious but very patient, you can try your hand at building one from Lego bricks.
Universal
You can construct lots of things with the right tape and table, and reasoning about them mathematically is easier than trying to reason about a full-blown computer — indeed that’s the point of the thought experiment. Here’s the kicker: it is possible to construct a universal Turing machine. That is, a machine that reads an arbitrary Turing machine description from a tape and simulates it. You can argue that such a machine forms the basis for the modern stored-program computer.
Your Turn
If you want to experiment with a Turing machine, you don’t have to resort to Lego bricks or a major hardware build. You can find simulators online. In addition, I put together some Excel spreadsheets that implement a Turing Machine that you can find on GitHub. Just be sure to enable macros after you load the spreadhsheet. You can see one of the spreadsheets below.
The top row lets you set the current state and the tape position (the highlighted block on the tape). You can also use the control buttons (there are two reset buttons to the right that you can’t see in the picture). You can edit the tape, of course, and the state table is at the bottom. You can use the Step button to run one cycle or the Execute button to run continuously. Be sure to save because if you press Execute and get caught in an endless loop, it is hard to stop (Control+Break should do it, but doesn’t always).
We recently looked at a pretty snazzy Turing build. You can see a video of that machine in action below.
You can do more than merely argue Turing machines form the basis for the modern stored-program computer. There are proofs that the two are equivalent (if you add an infinite storage peripheral). There are also proofs that modern languages are “Turing complete” – that is, you could construct a compiler for them to make Turing machines.
My 10 y/o daughter proved that even MIT Scratch is Turing complete simply by using it to implement a Universal Turing Machine. This is the key point, if you can prove that a Universal Turing Machine is in fact complete then any method that allows you to create that particular machine must also be complete.
However it is one thing to prove the above and another altogether to implement something even as simple as a Forth engine on the same machine.
Aha! Reflexive, Symmetric and Transitive properties college day bliss
Turing was a great man but I am disgusted at how my country treated him, He was chemically castrated instead of being sent to prison for being gay. This affected him so much that he took his own life at only 41. I just wonder what else he would have left future generations had he not been treated this way.
It is disgusting what the British Government did to him. You have to understand some of their thinking though, because our country stupidly made homosexuality a crime there was a very real risk that someone who was gay could be subject to blackmail. The authorities believed that they could remove that future risk by stopping him from being sexually active. Stupid times and I hope that future generations learn from these things.
I do understand the thinking homosexuality was viewed nearly as bad a paedophilia back then (mainly because of the church’s influence). It’s just such a shame that he was treated like this. Turing was a modern man stuck in an old days system.
That is true and matches one theory as to why all of the MPs ever convicted of paedophilia in Australia were associated with the Labor Party, the power brokers could expect 100% obedience from them because they knew their secret, but it does not in any way excuse their crimes, it just highlights the dangers of such potential compromises. Other groups collect evidence of young people using drugs or other unlawful conduct so that they can control them later in life. So yes without a doubt due to the mismatch between his uncontrollable urges and the society he lived in Turing was a huge security risk.
You do the crime you do the time, if he was so smart he should have know that, at least tried to keep his private life private instead of blabbing it out to the popo what did he expect was going to happen?
He chose the treatment and he had finished his chemical castration when he died, many believe it wasn’t the last desperate act of a tortured soul but just an unfortunate accident from his own experiments.
He might have been clever at stealing ideas from the poles and coming up with loads of AI nonsense but he didn’t have much in the way of common sense did he?
I have never seen a more regressive comment by anyone here on Hackaday. Your analysis of what Turning endured is barbaric and just as ignorant as the people of the time were.
He did not blithely blab about his lover, his home was broken into and after reporting the incident to police they uncovered his lover was present at the time of the burglary. He was faced with the destruction of his career by being jailed or to undergo an experimental procedure based on faulty science in an over-bloated fear of exploitation of a person who had high level secrets. You cannot under any version of the truth claim that he voluntarily underwent the procedure when faced with the alternative, especially when the supposed bright minds of the psychological field were claiming this treatment was an effective cure for homosexuality. It was a choice between two evils.
The conjecture about his death is just that, conjecture. It is hilarious that the wedge of doubt for the official version of his death is that the apple at his bedside was not tested for arsenic, yet the same carelessness is used finding alternate possibilities of his death. There is an air of cover-up surrounding these conspiracy theories about his death because the government can be more easily forgiven for doing such a reprehensible act to a genius of high-esteem if it appears he didn’t kill himself in the wake of the treatment.
Your attempt at de-legitimatizing his accomplishments is particularly reprehensible given the rest of your comment. Regardless of where the genesis of the enigma cracking machine originated, the fact is that Poland was occupied territory at this time and there was absolutely no way for the Polish team to continue work on it. It had to be done in Allied held territory but close enough to be close to the intercepted radio transmissions, so England was the only logical place to put it.
I nearly reported your comment but such an ignorant comment must be refuted rather than hidden.
From what i gather he was quite open about his sexuality and defiant when charged. I don’t understand what you mean about him not having a choice, his career was over either way. Two years in jail maximum isn’t too bad, are you saying he wasn’t clever enough to understand that hormone injections wouldn’t mess him up? I don’t think whether he killed himself or not is really relevant to the case i just thought it was interesting that it happened a year after the injections.
I don’t understand why you would report my comment in particular, it’s no more off topic than previous.
I am saying it is fundamentally inhumane to believe someone deserved to be chemically castrated regardless of what legal artifice is constructed to justify it. Cleverness has exactly zero correlation to deserving the treatment. If he was a drooling idiot it would still be inhumane, FULL STOP.
No amount of your arguments will change that fact, but please proceed guv’na.
As a Pole I can add few things to this discussion:
1) Germans were modifying Enigma. Original success of polish team was a little bit obsolete as early as in September of 1939, when Nazis invaded Poland. Further work was needed. Team went into exile to France, and after fall of Paris they were able to go to the UK. Before that, if I remember correctly, one of them (Rejewski) met up with Turing in Paris. Due to some incomprehensible reason they weren’t allowed to work in Bletchley Park!
2) Turing’s work since then was completely original. He wasn’t simply implementing polish solutions – he developed new ones, coping with new modifications introduced by Germans.
3) Turing’s work in Bletchley Park wasn’t limited to Enigma. He also developed means of cracking German teletype ciphers. Polish team had nothing to do with them. If I remember correctly during WW2 he was also involved in development of SIGSALY – early secure digital voice communication system.
Unfortunately there is popular notion among polish people, who believe that British intelligence robbed polish cryptographers from their achievements, and all the work done in Bletchley Park was merely plagiarism. Of course it is not that simple…
I nearly reported your comment because it reads like “bwwaaaaa!! agree with me or i’ll destroy you!!!!” :p
ahhh and there’s the politically correct hilarity trying to pound the opposition into conformity. nice use of code words like ‘regressive’ and tying a dissenting opinion to that of barbarism.
I would pose the question that you would beat everyone over the head and have their ideas conform with yours, but you also praise turing for presenting a dissenting opinion on sexuality. can’t have it both ways.
oh, and i nearly reported your comment because it reads like “BBWWWAAA!!! Agree with me or i’ll destroy you!”
Troll much?
oh boy you got me!
actually like any other reasonable person what i truly believe is that since we will never be able to live up to the standards of future generations we should just scrap all laws and legislation right now just in case someone in the future disagrees with it and thinks we are barbarians.
So I take it you were OK with slavery because it was lawful at the time?
Some minor quibbles. The symbols written on the tape are from a finite set and in fact a zero and a one are sufficient to do anything possible with a larger set of symbol. The infinite tape is comparable to infinite memory in a computer. The fact that any computation can be done with an infinite tape or an (infinite memory) is not the same as saying that practical computations can not be made with a finite tape. The rules on how to move the tape and rewrite the symbols are an analogue to the hardware that runs a modern computer. In this sense a Turing machine is simply another practical computer, it is just that using semiconductors are cheaper and practical in this world than using a rewritable tape and some kind of robot head. Look at https://en.wikipedia.org/wiki/Theory_of_computation to get a better overview or read Ullman’s classic book. The most intriguing result of Turing’s is the proof of the halting problem. This basically says that any computer or computer program (since all computers we have are Turing compatible and could be emulated on a Turing machine) has the capability of completely debugging another program and determining whether it will ever stop executing. In other words given any debugging program, we could write a second program that it would fail to debug. This is one of the easiest to understand Undecidability theorems, much easier for example than Godels theorem. For me and many students, it is an exciting concept to wrap the mind around and does not require an extensive math or computer background.
Weeellll…
Since we all knew, before we even got through the TITLE, where this was going to go, I might as well ask, much more relevantly–
“Yes, but will it run Windows 10?”
You’ll need a long tape, but, yes, it will. The more important question is “will you have any choice whether to run Windows 10?”
The scene from “The imitation game” where Turing explains to the computer the importance of self and responsibility in the control of such huge power and demands that it pick it’s own name and then it chooses ‘Optimus Prime’ and transforms into a jeep for the first time was poignant and awesome and a testament to what can be done with a proper actor and really well done CGI. They should never have cut it. Re-badging it from the prequel to a historical documentary was never going to work.
Ironic that the injections are the first step in a sex change! I have known of a few active individuals undergoing that change, didn’t seem to dampen their style.
Difference is choice. Someone who’s brain operates and identifies as male, suddenly getting a dose of estrogen or estradiol, will not behave or have the same effects as someone who identifies as female.The details are all part of that fuzzy “science” we call psychology.
Often destroys their ability to have sex though. Quite important if you love somebody. Growing tits is only a good thing when you actually want tits.
chemical castration is also a treatment for prostate cancer.
nobody said BF
Anyone who thinks Turing completeness means you can make anything big from something small, Please see:Turing Tarpit.