Turing's (still?) classified inference engine algorithm?

Question

Does anyone know the algorithm used by Turing's Colossus inference engine, so highly classified that the Brits kept it secret for decades after WW II?

Indeed, it may still be classified. Several years ago a colleague of mine, the late Robert Johnson, sent me an email response to my announcement about the Hutter Prize for Lossless Compression of Human Knowledge. Bob was the guy who designed the Burroughs zero address architecture used for so many years in banking (and incidentally invented magnetic ink used on checks). He certainly had a lot of background he didn't advertise, including classified work.

Computerdom does not have a lot of art in inference engines (making predictions). The most effective inference engine that I know of is the software done for Colossus, Turing's code breaking "computer" of WWII. The Brits still treat that software as classified even though the hardware has been declassified for years. So far as I know, nobody outside of UK knows the details of that software. My point here is that drawing understanding from natural languages is a relatively small art practiced mostly by cryptoanalysts. And my further point is that the natural language of interest (be it English, Chinese, Mayan or ...) has a major influence on how one (person or program) goes about doing analyses and making inferences. From a practical perspective, the Hutter challenge would be much more tractable for at least me if I could do it in Chinese. My first PhD student was Jun Gu who is currently Chief Information Scientist for PRC. His thesis was on efficient compression technologies. If you wish, you can share these thoughts with whomever you please.

Bob Johnson Prof. Emeritus Computer Science Univ. of Utah

Answer 1

This doesn't answer your question, but you may find clues in two wartime papers of Alan Turing which were formerly classified were declassified and published in the UK National Archives in 2015, and are now available on the arXiv:

Alan M. Turing, ‘The Applications of Probability to Cryptography’, UK National Archives HW 25/37, 1942, arXiv:1505.04714.

Alan M. Turing, ‘Paper on Statistics of Repetitions’, UK National Archives HW 25/38, 1942, arXiv:1505.04715.

It may be possible to reconstruct, from the principles enumerated therein, what algorithm Turing would have implemented in the Colossus to perform the feats it is known to have been able to perform.

Answer 2

My amateur understanding, osmosed from everything I've avidly read, is that Alan Turing independently discovered and applied Bayes theorem to the cracking of the M4 Enigma. Bayes theorem could be described as 'inference'.

Turing didn't have a direct hand in attacking Fish nor the building of Colossus but his probabilistic approach was adopted by the Newmanry who did. The Colossus was an electro-mechanical counter but the early attacks were by hand.

In 2007, when the newly reconstructed Colossus Mk 2 was commissioned at Bletchley Park, a tunny was transmitted in Germany, intercepted in Britain and successfully decoded by the Colossus. So sufficient programming is understood today to actually use the Colossus to decipher Fish. Exciting :)

During wartime and right up until the very present Bayes was very much out-of-favour in academia. Within the secrecy of the western cryptographic community, however, it was heartily embraced.

The Colossus 'software' was a plugboard. I find it intriguing that there may be ways to plug a Colossus to make inferences that aren't now rediscovered! It is exciting to imagine that there are shortcuts in applying Bayes that may not yet have been discovered publicly. If so, these would have dramatic impact on the very practical application of Bayes which is taking off right now with self-driving cars and all the rest...

Answer 3

Again this one's a little speculative but founded in some truth. Like the best lies.

1. Just because something is classified, doesn't necessarily imply that anyone's trying to deliberately keep it secret. It just hasn't been declassified yet. In 2011 the NSA declassified "Cryptology: Instruction Book on the Art of Secret Writing" published in 1809. Even the most fervent tin foil wearing types will find it difficult to explain that, other than they just didn't get round to it. I'm not really sure what anyone can learn from 200 year old cryptographic techniques.

2. There is a 100 year rule in the UK that can keep documents classified and exempt from Freedom of Information requests. Some of reasons /excuses are detailed in section 24, 26 and 27 of The National Archives Access to public records. (The real conspiratorial stuff in the missing section 25!) Any student of politics will appreciate that one of the most common reasons for invoking secrecy is for saving face and embarrassment. It won't be Alan's algorithms. I expect they're reasonably simple by contemporary standards. It will be the associated material and events. Alan Turing is extremely controversial in the UK given his personal life and pardon.

3. The most controversial aspect of Colossus is that it may have been connected with the "Did Churchill allow Pearl Harbour?" theory. And therefore there might be a tenuous connection to Alan's Ultra work and egg on the Government's face. Most current evidence does not support this conspiracy, including Independent, GCHQ and the Churchill Society. (But the society and GCHQ would say that though wouldn't they?) The main reason for the theory still having legs is the reward. Imagine if it were true. Britain won the war (from the very very brink of defeat) and gained the bomb.

There are other examples of long term and apparently unsupportable classifications listed here. You'll easily infer that the only sensible conclusion is the avoidance of embarrassment. It's a common theme throughout the six items. None of them are security related. JFK's "hanging length" or machine gunning 7000 of your own POWs? Long story short; I wouldn't expect to find anything cryptographically significant in Alan's algorithms. Perhaps they're just doodles he made during lunch.