– How did the Turing machine work?


I wanna know how Alan Turing’s computer worked, and in turn, how it was able to crack the German Enigma.
I’ve watched a few videos on it, but they all seem confusing.

In: 0


A Turing machine is a concept from computer science, not a physical computer. ([https://en.wikipedia.org/wiki/Turing_machine](https://en.wikipedia.org/wiki/Turing_machine) )

The first machines they used to crack Enigma were called Bombes ([https://en.wikipedia.org/wiki/Bombe](https://en.wikipedia.org/wiki/Bombe) ), and later in the war they built Colossus ([https://en.wikipedia.org/wiki/Colossus_computer](https://en.wikipedia.org/wiki/Colossus_computer) ).

Maybe you’re confusing to things:

– a “Turing machine”: an abstract concept of a device, which would be pointless to actually build, that Turing invented to be able to philosophize about what computers can and cannot do in principle. It involves a storage tape and a read/write head

– the “bombs” at Bletchley Park, which Turing and his colleagues designed and built to crack the Enigma code. They involved many clicking relays, hence the name.

The bombes were a development of an earlier Polish design (bomba). The thing to understand is that the engima machine worked by having several rotors which were set at the start of each message in some order and positions based on that day’s instructions. The rotors would then advance with each letter of the message.

The aim of the codebreakers was to find the starting order and positions for a given day, because then they could reverse the encryption and read all the messages for that day. They did this basically by brute force – trying lots of possible starting combinations and eliminating each one as it produced a contradiction. Specifically the codebreakers would produce a menu which was a sample of plaintext that was likely to appear in messages. This was run through the bombe, and a contradiction would occur for example if a letter was encoded as itself; something the enigma machine was unable to do.

The bombe itself is basically just lots of enigma machines combined so it can try lots of starting positions simultaneously.

A Turing machine takes a tape with some alphabet that the computer can read (to keep it simple, let’s just say the alphabet is 0 and 1). The computer reads the first number on the tape. The computer has already been told that if the first number is a 1, it’ll change it to a 0 and move on to the next number. The computer has also been told though that if the number is a 0, to just leave it alone and move on to the next number. Then it gets to the next number and in this position, the computer is told to turn it into a 1 if it’s 0 and leave it alone if its already 1. Then it goes on to the next position and so on and so on. Basically, it’s encoded with 3 bits of information for each position it’s looking at: consider what tape says, change it, move forwards or backwards on the tape. That is all a Turing machine is, but you can describe any modern day computer through a Turing machine (it’d just be a *very* complicated Turing machine).

[Here is an example of a Turing machine that can add in binary](https://i.imgur.com/ml3bVRZ.jpg) (note that this uses a 6 letter alphabet, 0, 1, A, B, X, and Y, to keep it simpler). The starting tape would look like B[first number in binary]A[second number in binary]B (e.g. B1010A110B). You start at Q0 in the top left and just follow the arrows to the next state based on what letter was changed. Once you get to Q67, you’re done. In the bottom-left, you’ll see what it looks like for the example tape B1010A110B to go through the whole machine.