{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T09:45:28Z","timestamp":1768297528587,"version":"3.49.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T00:00:00Z","timestamp":1560470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-14-C-0001"],"award-info":[{"award-number":["FA8750-14-C-0001"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-13-1-0333"],"award-info":[{"award-number":["N00014-13-1-0333"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-13- 1-0212"],"award-info":[{"award-number":["W911NF-13- 1-0212"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>As inductive inference and machine-learning methods in computer science see continued success, researchers are aiming to describe ever more complex probabilistic models and inference algorithms. It is natural to ask whether there is a universal computational procedure for probabilistic inference. We investigate the computability of conditional probability, a fundamental notion in probability theory, and a cornerstone of Bayesian statistics. We show that there are computable joint distributions with noncomputable conditional distributions, ruling out the prospect of general inference algorithms, even inefficient ones. Specifically, we construct a pair of computable random variables in the unit interval such that the conditional distribution of the first variable given the second encodes the halting problem. Nevertheless, probabilistic inference is possible in many common modeling settings, and we prove several results giving broadly applicable conditions under which conditional distributions are computable. In particular, conditional distributions become computable when measurements are corrupted by independent computable noise with a sufficiently smooth bounded density.<\/jats:p>","DOI":"10.1145\/3321699","type":"journal-article","created":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T12:56:40Z","timestamp":1560776200000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["On the Computability of Conditional Probability"],"prefix":"10.1145","volume":"66","author":[{"given":"Nathanael L.","family":"Ackerman","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cameron E.","family":"Freer","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel M.","family":"Roy","sequence":"additional","affiliation":[{"name":"University of Toronto, ON"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Roy","author":"Ackerman Nathanael L.","year":"2010","unstructured":"Nathanael L. Ackerman , Cameron E. Freer , and Daniel M . Roy . 2010 . On the computability of conditional probability. Retrieved from http:\/\/arxiv.org\/abs\/1005.3014v1. Nathanael L. Ackerman, Cameron E. Freer, and Daniel M. Roy. 2010. On the computability of conditional probability. Retrieved from http:\/\/arxiv.org\/abs\/1005.3014v1."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 26th IEEE Symposium on Logic in Computer Science (LICS\u201911)","author":"Ackerman Nathanael L.","unstructured":"Nathanael L. Ackerman , Cameron E. Freer , and Daniel M. Roy . 2011. Noncomputable conditional distributions . In Proceedings of the 26th IEEE Symposium on Logic in Computer Science (LICS\u201911) . IEEE Computer Society, 107--116. Nathanael L. Ackerman, Cameron E. Freer, and Daniel M. Roy. 2011. Noncomputable conditional distributions. In Proceedings of the 26th IEEE Symposium on Logic in Computer Science (LICS\u201911). IEEE Computer Society, 107--116."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90019-F"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(96)00017-6"},{"key":"e_1_2_1_5_1","first-page":"956","article-title":"Notions of probabilistic computability on represented spaces","volume":"14","author":"Bosserhoff Volker","year":"2008","unstructured":"Volker Bosserhoff . 2008 . Notions of probabilistic computability on represented spaces . J. Univ. Comput. Sci. 14 , 6 (2008), 956 -- 995 . Volker Bosserhoff. 2008. Notions of probabilistic computability on represented spaces. J. Univ. Comput. Sci. 14, 6 (2008), 956--995.","journal-title":"J. Univ. Comput. Sci."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.58"},{"key":"e_1_2_1_7_1","first-page":"318","article-title":"Computing over the reals: Foundations for scientific computing","volume":"53","author":"Braverman Mark","year":"2006","unstructured":"Mark Braverman and Stephen Cook . 2006 . Computing over the reals: Foundations for scientific computing . Notices Amer. Math. Soc. 53 , 3 (2006), 318 -- 329 . Mark Braverman and Stephen Cook. 2006. Computing over the reals: Foundations for scientific computing. Notices Amer. Math. Soc. 53, 3 (2006), 318--329.","journal-title":"Notices Amer. Math. Soc."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90060-D"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90036-B"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00013-1"},{"key":"e_1_2_1_11_1","unstructured":"Fran\u00e7ois G. Dorais Gerald Edgar and Jason Rute. 2013. Continuity on a measure one set versus measure one set of points of continuity. MathOverflow. Retrieved from http:\/\/mathoverflow.net\/q\/146063 (version: 2013-10-27).  Fran\u00e7ois G. Dorais Gerald Edgar and Jason Rute. 2013. Continuity on a measure one set versus measure one set of points of continuity. MathOverflow. Retrieved from http:\/\/mathoverflow.net\/q\/146063 (version: 2013-10-27)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/788018.788794"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00243-5"},{"key":"e_1_2_1_14_1","volume-title":"Mathematical Theory and Computational Practice: Proceedings of the 5th Conference on Computability in Europe (CiE","volume":"5635","author":"Cameron","year":"2009","unstructured":"Cameron E. Freer and Daniel M. Roy. 2009. Computable exchangeable sequences have computable de Finetti measures . In Mathematical Theory and Computational Practice: Proceedings of the 5th Conference on Computability in Europe (CiE 2009 ). (Lecture Notes in Computer Sciience), Klaus Ambos-Spies, Benedikt L\u00f6we, and Wolfgang Merkle (Eds.) , Vol. 5635 . Springer, 218--231. Cameron E. Freer and Daniel M. Roy. 2009. Computable exchangeable sequences have computable de Finetti measures. In Mathematical Theory and Computational Practice: Proceedings of the 5th Conference on Computability in Europe (CiE 2009). (Lecture Notes in Computer Sciience), Klaus Ambos-Spies, Benedikt L\u00f6we, and Wolfgang Merkle (Eds.), Vol. 5635. Springer, 218--231."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS\u201910)","author":"Cameron","year":"2010","unstructured":"Cameron E. Freer and Daniel M. Roy. 2010. Posterior distributions are computable from predictive distributions . In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS\u201910) . Y. W. Teh and M. Titterington (Eds.). JMLR: W8CP 9 ( 2010 ), 233--240. Cameron E. Freer and Daniel M. Roy. 2010. Posterior distributions are computable from predictive distributions. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS\u201910). Y. W. Teh and M. Titterington (Eds.). JMLR: W8CP 9 (2010), 233--240."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.06.011"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.054"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.05.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3023476.3023503"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00093-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03073-4_27"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.12.009"},{"key":"e_1_2_1_25_1","unstructured":"Mathieu Hoyrup and Crist\u00f3bal Rojas. 2011. Absolute continuity of measures and preservation of randomness. (2011). Retrieved from https:\/\/members.loria.fr\/MHoyrup\/abscont.pdf.  Mathieu Hoyrup and Crist\u00f3bal Rojas. 2011. Absolute continuity of measures and preservation of randomness. (2011). Retrieved from https:\/\/members.loria.fr\/MHoyrup\/abscont.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2040947.2040961"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.016"},{"key":"e_1_2_1_28_1","volume-title":"Foundations of Modern Probability","author":"Kallenberg Olav","unstructured":"Olav Kallenberg . 2002. Foundations of Modern Probability ( 2 nd ed.). Springer , New York . Olav Kallenberg. 2002. Foundations of Modern Probability (2nd ed.). Springer, New York.","edition":"2"},{"key":"e_1_2_1_29_1","volume-title":"Classical Descriptive Set Theory. Graduate Texts in Mathematics","author":"Kechris Alexander S.","unstructured":"Alexander S. Kechris . 1995. Classical Descriptive Set Theory. Graduate Texts in Mathematics , Vol. 156 . Springer-Verlag , New York . Alexander S. Kechris. 1995. Classical Descriptive Set Theory. Graduate Texts in Mathematics, Vol. 156. Springer-Verlag, New York."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03034-5_17"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.2307\/2267778"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Symposium on Algorithms and Complexity","author":"Donald","unstructured":"Donald E. Knuth and Andrew C. Yao. 1976. The complexity of nonuniform random number generation . In Proceedings of the Symposium on Algorithms and Complexity . Academic Press, New York, 357--428. Donald E. Knuth and Andrew C. Yao. 1976. The complexity of nonuniform random number generation. In Proceedings of the Symposium on Algorithms and Complexity. Academic Press, New York, 357--428."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"A. N. Kolmogorov. 1933. Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer.  A. N. Kolmogorov. 1933. Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer.","DOI":"10.1007\/978-3-642-49888-6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1973-0322920-7"},{"key":"e_1_2_1_36_1","unstructured":"T. Minka J. M. Winn J. P. Guiver and D. A. Knowles. 2010. Infer.NET 2.4. Microsoft Research Cambridge. Cambridge UK. Retrieved from http:\/\/research.microsoft.com\/infernet.  T. Minka J. M. Winn J. P. Guiver and D. A. Knowles. 2010. Infer.NET 2.4. Microsoft Research Cambridge. Cambridge UK. Retrieved from http:\/\/research.microsoft.com\/infernet."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.3233\/COM-13015"},{"key":"e_1_2_1_38_1","volume-title":"Descriptive Set Theory","author":"Moschovakis Yiannis N.","unstructured":"Yiannis N. Moschovakis . 2009. Descriptive Set Theory ( 2 nd ed.). Mathematical Surveys and Monographs, Vol . 155. American Mathematical Society , Providence, RI. Yiannis N. Moschovakis. 2009. Descriptive Set Theory (2nd ed.). Mathematical Surveys and Monographs, Vol. 155. American Mathematical Society, Providence, RI.","edition":"2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00292-8"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1029000631"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1572527"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200028073"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452044.1452048"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994897"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1642090.1642189"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/2100662.2100698"},{"key":"e_1_2_1_47_1","volume-title":"Computability in Analysis and Physics","author":"Pour-El Marian B.","unstructured":"Marian B. Pour-El and J. Ian Richards . 1989. Computability in Analysis and Physics . Springer-Verlag , Berlin . Marian B. Pour-El and J. Ian Richards. 1989. Computability in Analysis and Physics. Springer-Verlag, Berlin."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.2307\/2270581"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(88)90140-6"},{"key":"e_1_2_1_50_1","volume-title":"Conditional Measures and Applications","author":"Rao M. M.","unstructured":"M. M. Rao . 2005. Conditional Measures and Applications ( 2 nd ed.). Pure and Applied Mathematics, Vol . 271. Chapman 8 Hall\/CRC. M. M. Rao. 2005. Conditional Measures and Applications (2nd ed.). Pure and Applied Mathematics, Vol. 271. Chapman 8 Hall\/CRC.","edition":"2"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/28907"},{"key":"e_1_2_1_54_1","volume-title":"Theory of Statistics","author":"Schervish Mark J.","unstructured":"Mark J. Schervish . 1995. Theory of Statistics . Springer-Verlag , New York . Mark J. Schervish. 1995. Theory of Statistics. Springer-Verlag, New York."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200710010"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90131-7"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.08.003"},{"key":"e_1_2_1_58_1","volume-title":"Conditional Probability Distributions","author":"Tjur Tue","unstructured":"Tue Tjur . 1974. Conditional Probability Distributions . Institute of Mathematical Statistics , University of Copenhagen, Copenhagen, Denmark. Tue Tjur. 1974. Conditional Probability Distributions. Institute of Mathematical Statistics, University of Copenhagen, Copenhagen, Denmark."},{"key":"e_1_2_1_59_1","volume-title":"A Constructive Definition of Conditional Distributions","author":"Tjur Tue","unstructured":"Tue Tjur . 1975. A Constructive Definition of Conditional Distributions . Institute of Mathematical Statistics , University of Copenhagen, Copenhagen, Denmark. Tue Tjur. 1975. A Constructive Definition of Conditional Distributions. Institute of Mathematical Statistics, University of Copenhagen, Copenhagen, Denmark."},{"key":"e_1_2_1_60_1","volume-title":"Probability Based on Radon Measures","author":"Tjur Tue","unstructured":"Tue Tjur . 1980. Probability Based on Radon Measures . John Wiley 8 Sons Ltd ., Chichester, UK. Tue Tjur. 1980. Probability Based on Radon Measures. John Wiley 8 Sons Ltd., Chichester, UK."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90001-A"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00298-9"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/358357"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0523"},{"key":"e_1_2_1_65_1","unstructured":"A. K. Zvonkin and L. A. Levin. 1970. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Uspekhi Mat. Nauk 25 6 (156) (1970) 85--127.  A. K. Zvonkin and L. A. Levin. 1970. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Uspekhi Mat. Nauk 25 6 (156) (1970) 85--127."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3321699","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3321699","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3321699","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:39Z","timestamp":1750204479000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3321699"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,14]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3321699"],"URL":"https:\/\/doi.org\/10.1145\/3321699","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,14]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}