2
$\begingroup$

This is probably a computer science history question.

Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?

$\endgroup$
6
  • 1
    $\begingroup$ IMO, it occurs more frequently the other way: mathematical methods are invented but remain impractical until an efficient algorithm is found. E.g. FFT, Reed-Solomon error correcting codes. $\endgroup$
    – user16034
    Nov 3, 2022 at 21:09
  • 1
    $\begingroup$ @YvesDaoust, what makes you say RS error correcting codes were impractical for a while? $\endgroup$
    – kodlu
    Nov 3, 2022 at 21:11
  • 1
    $\begingroup$ @kodlu: efficient decoders took a few years to be found. en.wikipedia.org/wiki/… $\endgroup$
    – user16034
    Nov 3, 2022 at 21:35
  • 1
    $\begingroup$ @YvesDaoust, fair enough. The way Prof. Welch described it in class [I took another class not Coding theory from Prof. Reed] was that decoding algorithm was inefficient, his notes are still on the wayback machine if you are interested. web.archive.org/web/20100702224041/http://csi.usc.edu/PDF/… $\endgroup$
    – kodlu
    Nov 4, 2022 at 2:11
  • 1
    $\begingroup$ @kodlu: thanks. I'll be quite interested in a clean procedure to handle the erasures in the Euclidean algorithm for RS decoding :-) $\endgroup$
    – user16034
    Nov 4, 2022 at 7:56

1 Answer 1

2
$\begingroup$

The Ternary Golay Code has parameters $[n,k,d]_3=[11,6,5]_3$ and thus is a linear code over $\mathbb{Z}_3=\{0,1,2\}$ with $3^6=729$ codewords. It is perfect so that all the Hamming spheres of radius $2$ around codewords fill the whole space $\{0,1,2\}^{11}$ with no gaps left over. This means that the code has covering radius $2,$ any ternary string is at most Hamming distance 2 from a codeword.

This code was discovered by a Finnish football (soccer) enthusiast, which gives one a scheme of playing 729 guesses of 11 football matches (1 denotes home win, 0 denotes a draw and 2 denotes an away win) and being guaranteed to guess at least $11-2=9$ matches correctly.

https://www.wikiwand.com/en/Ternary_Golay_code#History_and_Applications

The code was also discovered by Marcel Golay 2 years later, and independently. It has beautiful mathematical structure. Unlike the related binary perfect Golay code which had direct applications to data quantization, as well as connections to Leech lattice and other structures, the alphabet of size 3 is not really practical for traditional computation.

However, recently, the ternary Golay code was applied to fault tolerant quantum computation via a method known as magic state distillation. See the paper https://arxiv.org/abs/2003.02717

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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