Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T04:26:28.041Z Has data issue: false hasContentIssue false
Series:   Elements in Applied Category Theory

Theoretical Computer Science for the Working Category Theorist

Published online by Cambridge University Press:  25 January 2022

Noson S. Yanofsky
Noson S. Yanofsky
Affiliation:
Brooklyn College, City University of New York

Summary

Using basic category theory, this Element describes all the central concepts and proves the main theorems of theoretical computer science. Category theory, which works with functions, processes, and structures, is uniquely qualified to present the fundamental results of theoretical computer science. In this Element, readers will meet some of the deepest ideas and theorems of modern computers and mathematics, such as Turing machines, unsolvable problems, the P=NP question, Kurt Gödel's incompleteness theorem, intractable problems, cryptographic protocols, Alan Turing's Halting problem, and much more. The concepts come alive with many examples and exercises.
Get access

Keywords

category theorycomputational modelscomputability theorycomplexity theory
Type
Element
Information
Series: Elements in Applied Category Theory
Online ISBN: 9781108872348
Publisher: Cambridge University Press
Print publication: 03 March 2022

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aaronson, Scott. 2013. Quantum Computing Since Democritus. Cambridge University Press.Google Scholar
Agrawal, Manindra, Kayal, Neeraj, and Saxena, Nitin. 2002. PRIMES is in P. Ann. of Math, 2, 781–793.Google Scholar
Arora, Sanjeev, and Barak, Boaz. 2009. Computational Complexity: A Modern Approach. Cambridge University Press.Google Scholar
Asperti, Andrea, and Longo, Giuseppe. 1991. Categories, Types, and Structures: An Introduction to Category Theory for the Working Computer Scientist. MIT Press.Google Scholar
Baez, J., and Stay, M. 2011. Physics, topology, logic and computation: a Rosetta Stone. Pages 95–172 of: New Structures for Physics, Coecke, Bob (ed). Lecture Notes in Physics, vol. 813. Springer.Google Scholar
Barr, Michael, and Wells, Charles. 1985. Toposes, Triples and Theories. Grundlehren der Mathematischen Wissenschaften, vol. 278. Springer.CrossRefGoogle Scholar
Barr, Michael, and Wells, Charles. 1999. Category Theory for Computing Science, Third edition. Les Publications CRM, Montreal.Google Scholar
Bénabou, Jean. 1967. Introduction to bicategories. Pages 1–77 of: Reports of the Midwest Category Seminar. Lecture Notes in Mathematics, vol. 47. Springer.CrossRefGoogle Scholar
Boolos, G.S., Burgess, J.P., and Jeffrey, R.C. 2007. Computability and Logic, Fifth edition. Cambridge University Press.Google Scholar
Cockett, J.R.B., and Hofstra, P.J.W. 2008. Introduction to Turing categories. Ann. Pure Appl. Logic, 156(2–3), 183–209.CrossRefGoogle Scholar
Coecke, Bob, and Kissinger, Aleks. 2017. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press.Google Scholar
Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford. 2009. Introduction to Algorithms, Third edition. MIT Press.Google Scholar
Cutland, Nigel. 1980. Computability: An Introduction to Recursive Function Theory. Cambridge University Press.Google Scholar
Davis, M., and Hersh, R. 1973. Hilbert’s 10th problem. Scientific American, 229 (Nov.), 84–91.CrossRefGoogle Scholar
Davis, Martin, Segal, Ron, and Weyuker, Elaine. 1994a. Computability, Complexity and Languages. Academic Press.Google Scholar
Davis, Martin D., Sigal, Ron, and Weyuker, Elaine J. 1994b. Computability, Complexity, and Languages, Second edition. Academic Press.Google Scholar
Dean, Walter. 2016. Computational Complexity Theory. In: The Stanford Encyclopedia of Philosophy, winter 2016 edition, Zalta, Edward N. (ed). Metaphysics Research Lab, Stanford University.Google Scholar
Di Paola, Robert A., and Heller, Alex. 1987. Dominical categories: recursion theory without elements. J. Symbolic Logic, 52(3), 594–635.Google Scholar
Diaz-Boïls, Joaquim. 2017. Categorical comprehensions and recursion. Journal of Logic and Computation, 27, 1607–1641.Google Scholar
Eilenberg, Samuel. 1974. Automata, Languages, and Machines. Vol. A. Academic Press.Google Scholar
Eilenberg, Samuel. 1976. Automata, Languages, and Machines. Vol. B. Academic Press.Google Scholar
Eilenberg, Samuel, and Elgot, Calvin. 1970. Recursiveness. Academic Press.Google Scholar
Fiadeiro, José Luiz. 2004. Categories for Software Engineering. Springer.Google Scholar
Garey, M.R., and Johnson, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co.Google Scholar
Gurski, Nick. 2011. Loop spaces, and coherence for monoidal and braided monoidal bicategories. Available at arXiv:1102.0981.Google Scholar
Ehrig, H., Kiermeier, K.-D., Kreowski, H.-J., and Kühnel, W. 1974. Universal Theory of Automata. A Categorical Approach. Teubner.Google Scholar
Harel, David. 2000. Computers Ltd.: What They Really Can’t Do. Oxford University Press, Inc.Google Scholar
Harrow, Keith. 1979. Theoretical and applied computer science: antagonism or symbiosis? Amer. Math. Monthly, 86(4), 253–260.Google Scholar
Hartmanis, J., and Hopcroft, J.E. 1976. Independence results in computer science. SIGACT News, 8(4), 13–24.Google Scholar
Heller, Alex. 1990. An existence theorem for recursion categories. J. Symbolic Logic, 55(3), 1252–1268.Google Scholar
Hodges, Andrew. 1983. Alan Turing: the Enigma. Simon & Schuster.Google Scholar
Hofstra, Pieter, and Scott, Philip. 2021. Aspects of categorical recursion theory. Downloaded from https://www.site.uottawa.ca/phil/papers on December 24, 2019.Google Scholar
Hopcroft, John E., and Ullman, Jeff D. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.Google Scholar
Immerman, Neil. 1998. Descriptive Complexity. Springer.Google Scholar
Kassel, Christian. 1995. Quantum Groups. Graduate Texts in Mathematics, vol. 155. Springer.CrossRefGoogle Scholar
Lambek, Joachim, and Scott, Philip. 1986. Introduction to Higher-Order Categorical Logic. Cambridge Studies in Advanced Mathematics, no. 7. Cambridge University Press.Google Scholar
Lawvere, F. William. 1969. Diagonal arguments and cartesian closed categories. Pages 134–145 of: Category Theory, Homology Theory and their Applications, II (Battelle Institute Conference, Seattle, Wash., 1968, Vol. Two). Springer.Google Scholar
Lawvere, F. William, and Rosebrugh, Robert. 2003. Sets for Mathematics. Cambridge University Press.Google Scholar
Lawvere, F. William, and Schanuel, Stephen H. 2009. Conceptual Mathematics: A First Introduction to Categories, Second edition. Cambridge University Press.Google Scholar
Leinster, Tom. 1998. Basic bicategories. Available at arXiv:math/9810017.Google Scholar
Lengyel, Florian. 2004. More existence theorems for recursion categories. Ann. Pure Appl. Logic, 125(1–3), 1–41.Google Scholar
Lewis, Harry R., and Papadimitriou, Christos H. 1997. Elements of the Theory of Computation, Second edition. Prentice Hall.Google Scholar
Libkin, Leonid. 2004. Elements of Finite Model Theory. Springer.Google Scholar
Longo, Giuseppe, and Moggi, Eugenio. 1984a. Cartesian closed categories of enumerations for effective type structures (Part I & II). Pages 235–255 in: Semantics of Data Types, Khan, G., MacQueen, D.B., and Plotkin, G. (eds) Lecture Notes in Computer Science, vol. 173. Springer.CrossRefGoogle Scholar
Longo, Giuseppe, and Moggi, Eugenio. 1984b. Gödel numberings, principal morphisms, combinatory algebras: A category-theoretic characterization of functional completeness. Pages 397–406 in: Mathematical Foundations of Computer Science 1984. MFCS 1984, Chytil, M.P., Koubek, V. (eds). Lecture Notes in Computer Science, vol. 176. Springer.Google Scholar
Longo, Giuseppe, and Moggi, Eugenio. 1990. A category-theoretic characterization of functional completeness. Theor. Comput. Sci., 70(2), 193–211.Google Scholar
Mac Lane, Saunders. 1998. Categories for the Working Mathematician, Second edition. Graduate Texts in Mathematics, vol. 5. Springer.Google Scholar
Manin, Yu. I. 2010. A Course in Mathematical Logic for Mathematicians, Second edition. Graduate Texts in Mathematics, vol. 53. Springer.CrossRefGoogle Scholar
Manin, Yuri I. 2000. Classical computing, quantum computing, and Shor’s factoring algorithm. Astérisque, 266, 375–404.Google Scholar
Mendelson, Elliott. 1997. Introduction to Mathematical Logic, Fourth edition. Chapman & Hall.Google Scholar
Otto, James R. 1995. Complexity Doctrines. Ph.D. Thesis, McGill University.Google Scholar
Papadimitriou, Christos H. 1994. Computational Complexity. Addison-Wesley.Google Scholar
Pavlovic, Dusko. 2013. Monoidal computer I: Basic computability by string diagrams. Information and Computation, 226(Supplement C), 94–116.Google Scholar
Pierce, Benjamin C. 1991. Basic Category Theory for Computer Scientists. MIT Press.Google Scholar
Poigné, Axel. 1992. Basic Category Theory. Pages 413–640 of: Handbook of Logic in Computer Science (Vol. 1), Abramsky, S., and Maibaum, T.S.E. (eds). Oxford University Press, Inc.Google Scholar
Rich, Elaine. 2008. Automata, Computability and Complexity: Theory and Applications. Pearson.Google Scholar
Rogers, Hartley Jr.. 1987. Theory of Recursive Functions and Effective Computability. MIT Press.Google Scholar
Román, Leopoldo. 1989. Cartesian categories with natural numbers object. J. Pure Appl. Algebra, 58(3), 267–278.Google Scholar
Rydeheard, David E., and Burstall, Rod M. 1988. Computational Category Theory. Prentice Hall.Google Scholar
Scott, P.J. 2000. Some aspects of categories in computer science. Pages 3–77 of: Handbook of Algebra, Vol. 2, Hazewinkel, M. (ed). North-Holland.Google Scholar
Seely, R.A.G. 1987. Modeling computations: a 2-categorical framework. Pages 65–71 of: Proc. Symposium on Logic in Computer Science, IEEE Computer Society,Google Scholar
Shannon, Claude E. 1956. A universal Turing machine with two internal states. Pages 157–165 of: Automata Studies. Annals of Mathematics Studies, no. 34. Princeton University Press.Google Scholar
Shor, Peter. W. 1994. Algorithms for quantum computation: discrete logarithms and factoring. Pages 124–134 of: Proc. 35th Annual Symposium on Foundations of Computer Science. IEEE Computer Society.Google Scholar
Shulman, Michael A. 2010. Constructing symmetric monoidal bicategories. Available at arXiv:1004.0993.Google Scholar
Sipser, Michael. 2006. Introduction to the Theory of Computation, Second edition. Course Technology.Google Scholar
Soare, Robert I. 1987. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer.Google Scholar
Spivak, David I. 2014. Category Theory for the Sciences. MIT Press.Google Scholar
Street, Ross. 1996. Categorical structures. Pages 529–577 of: Handbook of Algebra, Vol. 1. Elsevier/North-Holland.CrossRefGoogle Scholar
Turing, Alan. 1937. On computable numbers with an application to the Entschei-dungsproblem. Proceedings of the London Mathematical Society (2), 42, 230–265.CrossRefGoogle Scholar
UnivalentFoundationsProgram. 2013. Homotopy Type Theory–Univalent Foundations of Mathematics. https://homotopytypetheory.org/book, Institute for Advanced Study.Google Scholar
Walters, R.F.C. 1991. Categories and Computer Science. Cambridge University Press.Google Scholar
Yanofsky, Noson S. 2003. A universal approach to self-referential paradoxes, incompleteness and fixed points. Bull. Symbolic Logic, 9(3), 362–386.Google Scholar
Yanofsky, Noson S. 2011. Towards a definition of an algorithm. J. Logic Comput., 21(2), 253–286.Google Scholar
Yanofsky, Noson S. 2013. The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us. MIT Press.Google Scholar
Yanofsky, Noson S. 2015. Computability and Complexity of Categorical Structures. Available at http://www.sci.brooklyn.cuny.edu/noson/.Google Scholar
Yanofsky, Noson S. 2017. Galois theory of algorithms. Pages 323–347 of: Rohit Parikh on Logic, Language and Society, Başkent, C., Moss, L., Ramanujam, R. (eds). Outstanding Contributions to Logic, vol. 11. Springer.Google Scholar
Yanofsky, Noson S., and Mannucci, Mirco A. 2008. Quantum Computing for Computer Scientists. Cambridge University Press.Google Scholar

Save element to Kindle

To save this element to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Theoretical Computer Science for the Working Category Theorist
  • Noson S. Yanofsky, Brooklyn College, City University of New York
  • Online ISBN: 9781108872348
Available formats
×

Save element to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Theoretical Computer Science for the Working Category Theorist
  • Noson S. Yanofsky, Brooklyn College, City University of New York
  • Online ISBN: 9781108872348
Available formats
×

Save element to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Theoretical Computer Science for the Working Category Theorist
  • Noson S. Yanofsky, Brooklyn College, City University of New York
  • Online ISBN: 9781108872348
Available formats
×