License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.33
URN: urn:nbn:de:0030-drops-60558
Go to the corresponding LIPIcs Volume Portal

Papadimitriou, Christos H.

Computation as a Scientific Weltanschauung (Invited Talk)

LIPIcs-SWAT-2016-33.pdf (0.2 MB)


Computation as a mechanical reality is young - almost exactly seventy years of age - and yet the spirit of computation can be traced several millennia back. Any moderately advanced civilization depends on calculation (for inventory, taxation, navigation, land partition, among many others) - our civilization is the first one that is conscious of this reliance.

Computation has also been central to science for centuries. This is most immediately apparent in the case of mathematics: the idea of the algorithm as a mathematical object of some significance was pioneered by Euclid in the 4th century BC, and advanced by Archimedes a century later. But computation plays an important role in virtually all sciences: natural, life, or social. Implicit algorithmic processes are present in the great objects of scientific inquiry - the cell, the universe, the market, the brain - as well as in the models developed by scientists over the centuries for studying them. This brings about a very recent - merely a few decades old - mode of scientific inquiry, which is sometime referred to as the lens of computation: When students of computation revisit central problems in science from the computational viewpoint, often unexpected progress results. This has happened in statistical physics through the study of phase transitions in terms of the convergence of Markov chain-Monte Carlo algorithms, and in quantum mechanics through quantum computing.

This talk will focus on three other manifestations of this phenomenon. Almost a decade ago, ideas and methodologies from computational complexity revealed a subtle conceptual flaw in the solution concept of Nash equilibrium, which lies at the foundations of modern economic thought. In the study of evolution, a new understanding of century-old questions has been achieved through surprisingly algorithmic ideas. Finally, current work in theoretical neuroscience suggests that the algorithmic point of view may be invaluable in the central scientific question of our era, namely understanding how behavior and cognition emerge from the structure and activity of neurons and synapses.

BibTeX - Entry

  author =	{Christos H. Papadimitriou},
  title =	{{Computation as a Scientific Weltanschauung (Invited Talk)}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{33:1--33:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-60558},
  doi =		{10.4230/LIPIcs.SWAT.2016.33},
  annote =	{Keywords: Lens of computation, Nash equilibrium, neuroscience}

Keywords: Lens of computation, Nash equilibrium, neuroscience
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI