Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
Published online by Cambridge University Press: 05 June 2014
Edited by
Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Summary
Abstract. The problem of replicating the flexibility of human common-sense reasoning has captured the imagination of computer scientists since the early days of Alan Turing's foundational work on computation and the philosophy of artificial intelligence. In the intervening years, the idea of cognition as computation has emerged as a fundamental tenet of Artificial Intelligence (AI) and cognitive science. But what kind of computation is cognition?
We describe a computational formalism centered around a probabilistic Turing machine called QUERY, which captures the operation of probabilistic conditioning via conditional simulation. Through several examples and analyses, we demonstrate how the QUERY abstraction can be used to cast common-sense reasoning as probabilistic inference in a statistical model of our observations and the uncertain structure of the world that generated that experience. This formulation is a recent synthesis of several research programs in AI and cognitive science, but it also represents a surprising convergence of several of Turing's pioneering insights in AI, the foundations of computation, and statistics.
§1. Introduction. In his landmark paper Computing Machinery and Intelligence [Tur50], Alan Turing predicted that by the end of the twentieth century, “general educated opinion will have altered so much that one will be able to speak of machines thinking without expecting to be contradicted.” Even if Turing has not yet been proven right, the idea of cognition as computation has emerged as a fundamental tenet of Artificial Intelligence (AI) and cognitive science. But what kind of computation—what kind of computer program—is cognition?
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 195 - 252Publisher: Cambridge University PressPrint publication year: 2014
References
[AFR11] , , and , Noncomputable conditional distributions, Proceedings of the 26th annual IEEE symposium on Logic in Computer Science (LICS 2011), 20ll, pp. 107-116.
[And90] , The adaptive character of thought, Erlbaum, Hillsdale, NJ, 1990.
[AB13] and , Computability and analysis: The legacy of Alan Turing, in this volume.
[BJ03] and , Learning graphical models with Mercer kernels, Advances in Neural Information Processing Systems 15 (NIPS 2002) (, , and , editors), The MIT Press, Cambridge, MA, 2003, pp. 1009-1016.
[Bak12] , Bayesian theory of mind: Modeling human reasoning about beliefs, desires, goals, and social relations, Ph.D. thesis, Massachusetts Institute of Technology, 2012.
[BGT07] , , and , Theory-based social goal inference, Proceedings of the 30th annual conference of the Cognitive Science Society, 2007, pp. 1447-1452.
[BST09] , , and , Action understanding as inverse planning, Cognition, vol. 113 (2009), no. 3, pp. 329-349.Google Scholar
[Bar98] , Information-theoretic characterization of Bayes performance and the choice ofpriors in parametric and nonparametric problems, Bayesian statistics 6: Proceedings of the sixth Valencia international meeting (, , , and , editors), 1998, pp. 27-52.
[Be157] , Dynamic programming, Princeton University Press, Princeton, NJ, 1957.
[B1a97] , Domain representability of metric spaces, Annals of Pure and Applied Logic, vol. 83 (1997), no. 3, pp. 225-247.Google Scholar
[Cam11] , Behavioral game theory: Experiments in strategic interaction, The Roundtable Series in Behavioral Economics, Princeton University Press, 2011.
[Car09] , The origin of concepts, Oxford University Press, New York, 2009.
[CSH08] , , and , Complexity of inference in graphical models, Proceedings of the twenty fourth conference on Uncertainty in Artificial Intelligence (UAI 2008) (Corvalis, Oregon), AUAI Press, 2008, pp. 70-78.
[Coo90] , The computational complexity of probabilistic inference using Bayesian belief networks, Artificial Intelligence, vol. 42 (1990), no. 2–3, pp. 393-405.Google Scholar
[Cop04] (editor), The essential Turing: Seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life: Plus the secrets of enigma, Oxford University Press, Oxford, 2004.
[CP96] and , On Alan Turing's anticipation of connectionism, Synthese, vol. 108 (1996), no. 3, pp. 361-377.Google Scholar
[DKLR00] , , , and , An optimal algorithm for Monte Carlo estimation, SIAM Journal on Computing, vol. 29 (2000), no. 5, pp. 1484-1496.Google Scholar
[DL93] and , Approximating probabilistic inference in Bayesian belief networks is NP-hard, Artificial Intelligence, vol. 60 (1993), no. 1, pp. 141-153.Google Scholar
[dMSS56] , , , and , Computability by probabilistic machines, Automata Studies, Annals of Mathematical Studies, no. 34, Princeton University Press, Princeton, NJ, 1956, pp. 183-212.
[DeG05] , Optimal statistical decisions, Wiley Classics Library, Wiley, 2005.
[DWRT10] , , , and , Nonparametric Bayesian policy priors for reinforcement learning, Advances in Neural Information Processing Systems 23 (NIPS 2010) (, , , , and , editors), 2010, pp. 532-540.
[Eda96] , The Scott topology induces the weak topology, 11th annual IEEE symposium on Logic in Computer Science (LICS 1996), IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 372-381.
[EH98] and , A computational model for metric spaces, Theoretical Computer Science, vol. 193 (1998), no. 1–2, pp. 53-73.Google Scholar
[FG12] and , Predicting pragmatic reasoning in language games, Science, vol. 336 (2012), no. 6084, p. 998.Google Scholar
[Gac05] , Uniform test of algorithmic randomness over a general space, Theoretical Computer Science, vol. 341 (2005), no. 1–3, pp. 91-137.Google Scholar
[GHR10] , , and , Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Information and Computation, vol. 208 (2010), no. 1, pp. 23-41.Google Scholar
[Gei84] , Physical limits of acuity and hyperacuity, Journal of the Optical Society of America A, vol. 1 (1984), no. 7, pp. 775-782.Google Scholar
[GG12] and , Ping pong in Church: Productive use of concepts in human probabilistic inference, Proceedings of the thirty-fourth annual conference of the Cognitive Science Society (Austin, TX) (, , and , editors), Cognitive Science Society, 2012.
[GGLT12] , , , and , Noisy Newtons: Unifying process and dependency accounts of causal attribution, Proceedings of the thirty-fourth annual conference of the Cognitive Science Society (Austin, TX) (, , and , editors), Cognitive Science Society, 2012.
[GT07] and , Introduction to statistical relational learning, The MIT Press, 2007.
[GG02] and , Models of ecological rationality: The recognition heuristic, Psychological Review, vol. 109 (2002), no. 1, pp. 75-90.Google Scholar
[Goo61] , A causal calculus. I, The British Journal for the Philosophy of Science, vol. 11 (1961), pp. 305-318.Google Scholar
[Goo68] , Corroboration, explanation, evolving probability, simplicity and a sharpened razor, The British Journalfor the Philosophy of Science, vol. 19 (1968), no. 2, pp. 123-143.Google Scholar
[Goo75] , Explicativity, corroboration, and the relative odds of hypotheses, Synthese, vol. 30 (1975), no. 1, pp. 39-73.Google Scholar
[Goo79] , A. M. Turing's statistical work in World War II, Biometrika, vol. 66 (1979), no. 2, pp. 393-396, Studies in the history of probability and statistics. XXXVII.Google Scholar
[Goo91] , Weight of evidence and the Bayesian likelihood ratio, The use of statistics in forensic science ( and , editors), Ellis Horwood, Chichester, 1991.
[Goo00] , Turing's anticipation of empirical Bayes in connection with the cryptanalysis of the naval Enigma, Journal of Statistical Computation and Simulation, vol. 66 (2000), no. 2, pp. 101-111.Google Scholar
[GBT09] , , and , Cause and intent: Social reasoning in causal learning, Proceedings of the 31st annual conference of the Cognitive Science Society, 2009, pp. 2759-2764.
[GMRBT08] , , , , and , Church: A language for generative models, Proceedings of the twenty-fourth conference on Uncertainty in Artificial Intelligence (UAI 2008) (Corvalis, Oregon), AUAI Press, 2008, pp. 220-229.
[GS12] and , Knowledge and implicature: Modeling language understanding as social cognition, Proceedings of the thirty-fourth annual Conference of the Cognitive Science Society (Austin, TX) (, , and , editors), Cognitive Science Society, 2012.
[GT12] and , The probabilistic language of thought, in preparation, 2012.
[GTFG08] , , , and , A rational analysis of rule-based concept learning, Cognitive Science, vol. 32 (2008), no. 1, pp. 108-154.Google Scholar
[GTO11] , , and , Probabilistic models of cognition, Church wiki, (2011), http://projects.csail.mit.edu/church/wiki/Probabilistic_Models-of-Cognition.
[GUT11] , , and , Learning a theory of causality, Psychological Review, vol. 118 (2011), no. 1, pp. 110-119.Google Scholar
[Gop12] , Scientific thinking in young children: Theoretical advances, empirical research, and policy implications, Science, vol. 337 (2012), no. 6102, pp. 1623-1627.Google Scholar
[GKT08] , , and , Bayesian models of cognition, Cambridge handbook of computational cognitive modeling, Cambridge University Press, 2008.
[GT05] and , Structure and strength in causal induction, Cognitive Psychology, vol. 51 (2005), no. 4, pp. 334-384.Google Scholar
[GT06] and , Optimal predictions in everyday cognition, Psychological Science, vol. 17 (2006), no. 9, pp. 767-773.Google Scholar
[GT09] and , Theory-based causal induction, Psychological Review, vol. 116 (2009), no. 4, pp. 661-716.Google Scholar
[GSW07] , , and , Computable metrization, Mathematical Logic Quarterly, vol. 53 (2007), no. 4–5, pp. 381-395.Google Scholar
[Ham12] , Physical reasoning in complex scenes is sensitive to mass, Master of Engineering thesis, Massachusetts Institute of Technology, Cambridge, MA, 2012.
[HBT11] , , and , Internal physics models guide probabilistic judgments about object dynamics, Proceedings of the thirty-third annual Conference of the Cognitive Science Society (Austin, TX) (, , and , editors), Cognitive Science Society, 2011, pp. 1545-1550.
[Hem02] , Effective metric spaces and representations of the reals, Theoretical Computer Science, vol. 284 (2002), no. 2, pp. 347-372.Google Scholar
[Hod97] , Turing: A natural philosopher, Phoenix, London, 1997.
[How60] , Dynamic programming and Markov processes, The MIT Press, Cambridge, MA, 1960.
[KLC98] , , and , Planning and acting in partially observable stochastic domains, Artificial Intelligence, vol. 101 (1998), pp. 99-134.Google Scholar
[KLM96] , , and , Reinforcement learning: A survey, Journal of Artificial Intelligence Research, vol. 4 (1996), pp. 237-285.Google Scholar
[Kal02] , Foundations of moden probability, 2nd ed., Probability and its Applications, Springer, New York, 2002.
[KGT08] , , and , Learning and using relational theories, Advances in Neural Information Processing Systems 20 (NIPS 2007), 2008.
[KSBT07] , , , and , Combining causal and similarity-based reasoning, Advances in Neural Information Processing Systems 19 (NIPS 2006) (, , and , editors), The MIT Press, Cambridge, MA, 2007, pp. 681-688.
[KT08] and , The discovery of structurai form, Proceedings of the National Academy of Sciences, vol. 105 (2008), no. 31, pp. 10687-10692.Google Scholar
[KY03] and , Bayesian models of object perception, Current Opinion in Neurobiology, vol. 13 (2003), no. 2, pp. 150-158.Google Scholar
[LBFL93] , , , and , DENDRAL: A case study of the first expert system for scientific hypothesis formation, Artificial Intelligence, vol. 61 (1993), no. 2, pp. 209-261.Google Scholar
[Luc59] , Individual choice behavior, John Wiley, New York, 1959.
[Luc77] , The choice axiom after twenty years, Journal of Mathematical Psychology, vol. 15 (1977), no. 3, pp. 215-233.Google Scholar
[Mac03] , Information theory, inference, and learning algorithms, Cambridge University Press, Cambridge, UK, 2003.
[MHC03] , , and , On the undecidability of probabilistic planning and related stochastic optimization problems, Artificial Intelligence, vol. 147 (2003), no. 1–2, pp. 5-34.Google Scholar
[Man09] , Natively probabilistic computation, Ph.D. thesis, Massachusetts Institute of Technology, 2009.
[Man11] , Beyond calculation: Probabilistic computing machines and universal stochastic inference, NIPS Philosophy and Machine Learning Workshop, (2011).
[MJT08] , , and , Stochastic digital circuits for probabilistic inference, Technical Report MIT-CSAIL-TR-2008-069, Massachusetts Institute of Technology, 2008.
[MKTG06] , , , and , Structured priors for structure learning, Proceedings of the twenty-second conference on Uncertainty in Artificial Intelligence (UAI2006) (Arlington, Virginia), AUAI Press, 2006, pp. 324-331.
[MR13] and , Stochastic inference machines, in preparation.
[Mar82] , Vision, Freeman, San Francisco, 1982.
[McC68] , Programs with common sense, Semantic information processing, The MIT Press, 1968, pp. 403-418.
[MUSTT12] , , , , and , Why blame Bob? Probabilistic generative models, counterfactual reasoning, and blame attribution, Proceedings of the thirty-fourth annual conference of the Cognitive Science Society (Austin, TX) (, , and , editors), Cognitive Science Society, 2012.
[MP43] and , A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biology, vol. 5 (1943), no. 4, pp. 115-133.Google Scholar
[Mon82] , A survey of partially observable Markov Decision Processes: Theory, models, andalgorithms, Management Science, vol. 28 (1982), no. 1, pp. 1-16.Google Scholar
[Mug91] , Inductive logic programming, New Generation Computing, vol. 8 (1991), no. 4, pp. 295-318.Google Scholar
[OC98] and (editors), Rational models of cognition, Oxford University Press, Oxford, 1998.
[OC07] and (editors), Bayesian rationality: The probabilistic approach to human reasoning, Oxford University Press, New York, 2007.
[PT87] and , The complexity of Markov Decision Processes, Mathematics of Operations Research, vol. 12 (1987), no. 3, pp. 441-450.Google Scholar
[Pea88] , Probabilistic reasoning in intelligent systems: Networks of plausible inference, Morgan Kaufmann, San Francisco, 1988.
[Pea04] , Graphical models for probabilistic and causal reasoning, Computer science handbook (, editor), CRC Press, 2nd ed., 2004.
[Pfa79] , Conditional distributions as derivatives, The Annals of Probability, vol. 7 (1979), no. 6, pp. 1046-1050.Google Scholar
[Rao88] , Paradoxes in conditional probability, Journal of Multivariate Analysis, vol. 27 (1988), no. 2, pp. 434-446.Google Scholar
[Rao05] , Conditional measures and applications, 2nd ed., Pure and Applied Mathematics, vol. 271, Chapman & Hall/CRC, Boca Raton, FL, 2005.
[RH11] and , A philosophical treatise of universal induction, Entropy, vol. 13 (2011), no. 6, pp. 1076-1136.Google Scholar
[Roy11] , Computability, inference and modeling in probabilistic programming, Ph.D. thesis, Massachusetts Institute of Technology, 2011.
[Sch07] , Admissible representations for probability measures, Mathematical Logic Quarterly, vol. 53 (2007), no. 4–5, pp. 431-445.Google Scholar
[Sch12] , The origins of inquiry: Inductive inference and exploration in early childhood, Trends in Cognitive Sciences, vol. 16 (2012), no. 7, pp. 382-389.Google Scholar
[She87] , Toward a universal law of generalization for psychological science, Science, vol. 237 (1987), no. 4820, pp. 1317-1323.Google Scholar
[SMH+91] , , , , , , and , Probabilistic diagnosis using a reformulation of the INTERNIST-1/QMR knowledge base, Methods of Information in Medicine, vol. 30 (1991), pp. 241-255.Google Scholar
[SG92] and , Bayesian statistics without tears: A sampling-resampling perspective, The American Statistician, vol. 46 (1992), no. 2, pp. 84-88.Google Scholar
[Sol64] , A formal theory of inductive inference: Parts I and II, Information and Control, vol. 7 (1964), no. 1, pp. 1–22 and 224-254.Google Scholar
[SG13] and , Reasoning about reasoning by nested conditioning: Modeling theory ofmind with probabilistic programs, submitted.
[SG12] , A dynamic programming algorithm for inference in recursive probabilistic programs, Second Statistical Relational AI workshop at UAI 2012 (StaRAI-12), (2012).Google Scholar
[TG01] and , Generalization, similarity, and Bayesian inference, Behavioral and Brain Sciences, vol. 24 (2001), no. 4, pp. 629-640.Google Scholar
[TGK06] , , and , Theory-based Bayesian models of inductive learning and reasoning, Trends in Cognitive Sciences, vol. 10 (2006), no. 7, pp. 309-318.Google Scholar
[TKGG11] , , , and , How to grow a mind: Statistics, structure, andabstraction, Science, vol. 331 (2011), no. 6022, pp. 1279-1285.Google Scholar
[Teu02] , Turing's connectionism: An investigation of neural network architectures, Springer-Verlag, London, 2002.
[Tju74] , Conditional probability distributions, Lecture Notes, no. 2, Institute of Mathematical Statistics, University of Copenhagen, Copenhagen, 1974.
[Tju75] , A constructive definition of conditional distributions, Preprint 13, Institute of Mathematical Statistics, University of Copenhagen, Copenhagen, 1975.
[Tju80] , Probability based on Radon measures, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons Ltd., Chichester, 1980.
[THS06] , , and , Probabilistic inference for solving (PO)MDPs, Technical Report EDI-INF-RR-0934, University of Edinburgh, School of Informatics, 2006.
[Tur36] , On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society. Second Series, vol. 42 (1936), no. 1, pp. 230-265.Google Scholar
[Tur39] , Systems of logic based on ordinals, Proceedings of the London Mathematical Society. Second Series, vol. 45 (1939), no. 1, pp. 161-228.Google Scholar
[Tur48] , Intelligent machinery, National Physical Laboratory Report, 1948.
[Tur52] , The chemical basis of morphogenesis, Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences, vol. 237 (1952), no. 641, pp. 37-72.Google Scholar
[Tur96] , Intelligent machinery, a heretical theory, Philosophia Mathematica. Philosophy of Mathematics, its Learning, andits Applications. Series III, vol. 4 (1996), no. 3, pp. 256-260, Originally a radio presentation, 1951.Google Scholar
[Tur12] , The applications of probability to cryptography, c. 1941, UK National Archives, HW25/37, 2012.
[UBM+09] , , , , , and , Help or hinder: Bayesian models of social goal inference, Advances in Neural Information Processing Systems 22 (NIPS2009), 2009, pp. 1874-1882.
[Wat89] , Learning from delayed rewards, Ph.D. thesis, King's College, University of Cambridge, 1989.
[Wei93] , Computability on computable metric spaces, Theoretical Computer Science, vol. 113 (1993), no. 2, pp. 191-210.Google Scholar
[Wei99] , Computability on the probability measures on the Borel sets of the unit interval, Theoretical Computer Science, vol. 219 (1999), no. 1–2, pp. 421-437.Google Scholar
[Wei00] , Computable analysis: An introduction, Texts in Theoretical Computer Science, An EATCS Series, Springer-Verlag, Berlin, 2000.
[WGRKT11] , , , , and , Bayesian policy search with policy priors, Proceedings of the twenty-second International Joint Conference on Artificial Intelligence (IJCAI) (Menlo Park, CA) (, editor), AAAI Press, 2011.
[WGSS11] , , , and , Nonstandard interpretations of probabilistic programs for efficient inference, Advances in Neural Information Processing Systems 24 (NIPS 2011), 2011.
[WSG11] , , and , Lightweight implementations of probabilistic programming languages via transformational compilation, Proceedings of the fourteenth international conference on Artificial Intelligence and Statistics (AISTATS), Journal of Machine Learning Research: Workshop and Conference Proceedings, vol. 15, 2011, pp. 770-778.
[Yam99] , Polynomial time samplable distributions, Journal of Complexity, vol. 15 (1999), no. 4, pp. 557-574.Google Scholar
[Zab95] , Alan Turing and the central limit theorem, American Mathematical Monthly, vol. 102 (1995), no. 6, pp. 483-494.Google Scholar
[Zab12] , Commentary on Alan M. Turing: The applications of probability to cryptography, Cryptologia, vol. 36(2012), no. 3, pp. 191-214.Google Scholar
- 3
- Cited by