Algorithmic lens as Alan Turing’s wider impact

Today is Alan Turing’s birthday. He would have turned 106.

It has been too long since I last wrote about him on TheEGG. Today, I want to provide an overview of some of his most important work based on my and other’s answers on this old cstheory question. This will build slightly on a post I wrote two years ago for the Heidelberg Laureate Forum, but it will share a lot of text in common.

Turing is far from obscure. Every computer scientist and programmer has heard his name. The Nobel prize of Computer Science is named after him. He has even joined the ranks of mathematicians with feature-length films. Although a film that misrepresents much history. But even outside of film, I feel that our perceptions and representations of Turing are shaped too heavily by the current boundaries and constraints of computer science. Or at least how computer science is popularly (mis)understood.

Also, it is just easier to film the building a giant machine than about proving theorems and revolutionizing how we think about the world.

As the great breadth of his work shows, Turing would not recognize the disciplinary boundaries that confine computer science to technology. Like Abel Molina, he would see many motivations for computer science, from Science and Technology to Mathematics and Philosophy to Society. Turing viewed the whole world through the algorithmic lens. A wide ambition that is sometimes lacking in modern computer science.

In this post, I want to highlight some of the aspects of the world that Turing looked at.

Turing was central to defining algorithms and computability, thus he was one of the people that helped assemble the algorithmic lens. As such, he had numerous contributions to what we currently view as computer science. He defined the Turing machine, and influenced his student — Robin Gandy — to build the dominant physicalist interpretation of the Church-Turing thesis. He made explicit the Halting problem, and with it the limits of computation and our understanding. He made computer science capable of radical abstraction: he showed that the details of how computers are realized physically is not essential for reasoning about the properties of problems they can solve.

In his PhD thesis, Turing introduced the central tools of computational complexity: oracles and relativization. He introduced concrete procedures like LU matrix decomposition (1948) and recognized the importance of numerical stability of algorithms. In 1949, he took the recognition of error further, developing what would become unit testing. In 1952, he was the first to come up with a ‘paper algorithm’ for chess. Opening a rich vein of problems for early AI. A vein we’re still mining to great gain — although no we’ve switched from Chess to Go.

However, I think his biggest contribution was viewing science through the algorithmic lens and not just computation for the sake of computation. He showed that any process can be fruitfully viewed as a computation.

During WW2, along with his colleagues, Turing used the idea of computation and electro-mechanical (as opposed to human) computers to help create the Turing–Welchman bombe and other tools and formal techniques for doing crypto-analysis. He started the transformation of cryptology — the art-form — to cryptography — the science — that Claude Shannon completed. Alan Turing viewed cryptology through algorithmic lenses. During his time at Bletchley Park, Turing also contributed to statistics, defining — with his assistant I. J. Good (1953) — the Good-Turing estimator for the probability of encountering an object of a hitherto unseen species, given a set of past observations of objects from different species.

In 1948, Turing followed his interested in the brain, to create the first learning artificial neural network. Unfortunately his manuscript was rejected by the director of the National Physical Laboratory and not published. At least not until 1967, well after his death and the publication of other neural networks. However, it predated both Hebbian learning (1949) and Rosenblatt’s perceptrons (1957) that we typically associated with being the first neural networks. Turing foresaw the foundation of connectionism — still a huge paradigm in cognitive science — and computational neuroscience. Alan Turing viewed the brain through algorithmic lenses. Descendants of similar networks are now the most popular topic in Machine Learning. Although direct influence cannot be traced to Turing — no doubt due in part to the shortsightedness of his director in not publishing Turing’s 1948 work.

However, Turing is still a central influence on AI. In 1950, Turing published his famous Computing machinery and intelligence and launched AI. This had a transformative effect on Psychology and Cognitive Science, where cognition as computation on internal representations still remains as the central dogma. Alan Turing viewed the mind through algorithmic lenses. By defining the Turing test, he also made a great contribution to instrumentalism and operationalization as an empirical abstraction. Since then the Turing test has been adapted and extended to other domains — Boris Bukh even proposed the economic Turing test for game theory. Although he did not have time to push deeper into the social sciences, other have built up an algorithmic view of economics, finance, and other parts of the social sciences. Given the over-sized role that social algorithms play in our society, this direction could benefit from even more attention through the algorithmic lens.

Finally, in 1952 Turing published The Chemical Basis of Morphogenesis. This has become his most cited work. In it, he asked (and started to answer) the question: how does a spherically symmetric embryo develop into a non-spherically symmetric organism under the action of symmetry-preserving chemical diffusion of morphogens? His approach in this paper was very physics-y, but some of it did have an air of theoretical computer science. His paper made rigorous qualitative statements (valid for various constants and parameters) instead of quantitative statements based on specific (in some fields: potentially impossible to measure) constants and parameters. Shortly before his death, he was continuing this study by working on the basic ideas of what was to become artificial life simulations, and a more discrete and non-differential-equation-based treatment of biology. In am earlier blog post I speculated on how he would develop biology if he had more time. Alan Turing started to view biology through algorithmic lenses.

Of course, this list is not exhaustive. As Scott Aaronson said on cstheory: asking for Alan Turing’s contributions to computer science “is a lot like asking for Newton’s contributions to physics, or Darwin’s to biology!”. He is foundational. And just like Newton and Darwin, Turing introduced not only an advance to his own field but gave us a new philosophical perspective. An algorithmic philosophy. I think Turing’s greatest (and often ignored) contribution to computer science was showing that we can glean great insight by viewing science and society through the algorithmic lens. My hope is that we continue this tradition.

If you are interested in any specific topic above, dear reader, then let me know in the comments. I’ll try to expand on those topic — to what extent I can — in future posts. They each deserve more than just a passing sentence, but I wanted this post to be compact.

References

Good, I. J. (1953). The population frequencies of species and the estimation of population parameters. Biometrika, 40(3-4): 237-264.

Hebb, D. O. (1949). The organization of behavior: A neuropsychological theory. Psychology Press.

Rosenblatt, F. (1957). The perceptron, a perceiving and recognizing automaton. Project Para. Cornell Aeronautical Laboratory.

Turing, A. M. (1948). Rounding-off errors in matrix processes. The Quarterly Journal of Mechanics and Applied Mathematics, 1(1): 287-308.

Turing, A. (1949). Checking a large routine. In The early British computer conferences (1989; pp. 70-72). MIT Press.

Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59(236): 433-460.

Turing, A. M. (1952). The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society of London B: Biological Sciences, 237(641): 37-72.

Advertisements

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

2 Responses to Algorithmic lens as Alan Turing’s wider impact

  1. lib says:

    Well, I’d like you to expand on his view of biology through algorithmic lenses. It would be really interesting coming from you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.