10
$\begingroup$

I am reading Turing's "Computing machinery and intelligence" paper (https://www.csee.umbc.edu/courses/471/papers/turing.pdf) and found a fragment in which he says:

I have set up on the Manchester computer a small programme using only 1,000 units of storage, whereby the machine supplied with one sixteen-figure number replies with another within two seconds. I would defy anyone to learn from these replies sufficient about the programme to be able to predict any replies to untried values.

It looks like a machine learning problem to me :) but putting my interest on AI aside, my question is the following:

Does anyone know what this program was doing?

I am very curious.

PS: By the length of the input and output, I suspect it was an encryption algorithm, but I would appreciate any clue to the actual program.

$\endgroup$
2
$\begingroup$

You're right that this has to do with encryption, but it's not encryption per se. It's something called hashing. What his program does is take a number, hash it, and output the hash. What Turing created is now called a cryptographically secure hash.

A modern cryptographically secure hash must do the following. It should be easy to hash the input, but very difficult to 'unhash' an output to get the input. In this case, "very difficult" usually means "it would take months or years on a supercomputer, if not even longer."

$\endgroup$
3
  • $\begingroup$ We usually think of a hash as having unbounded domain, whereas in this case, the domain and range are the same. In that sense, it's more like a one-way function. However, both a hash and a one-way function are actually easy to compute, whereas here the point is that it looks random, like a pseudorandom function. $\endgroup$ Aug 1 '17 at 7:24
  • 2
    $\begingroup$ Thanks @JorgePerez! I know what a hash is, my question was more like: what hash did he implement? Are there any notes on this? Maybe he published the algorithm? Sorry if I was not clear :) $\endgroup$
    – nanaki
    Aug 1 '17 at 9:40
  • 2
    $\begingroup$ Do you have a reference you can cite? $\endgroup$
    – Raphael
    Aug 1 '17 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.