HackerPapers

arXiv:1710.03090cs.LO

Theoretical Computer Science for the Working Category Theorist

Noson S. Yanofsky

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

Theoretical computer science discusses foundational issues about computations. It asks and answers questions such as "What is a computation?", "What is computable?", "What is efficiently computable?","What is information?", "What is random?", "What is an algorithm?", etc. We will present many of the major themes and theorems with the basic language of category theory. Surprisingly, many interesting theorems and concepts of theoretical computer science are easy consequences of functoriality and composition when you look at the right categories and functors connecting them.

arXiv comments
47 pages
Journal reference
DOI
Subjects
cs.LOLogic in Computer Science cs.CCComputational Complexity math.CTCategory Theory

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Oct 2017 to Oct 2017. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.