You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Noah Chrein (May 06 2020 at 16:57):Tomorrow will be the final meeting of this semester's Applied Category Theory Seminar. @Noson S. Yanofsky will give us a preview of his upcoming book "Theoretical Computer Science for the Working Category Theorist". As a member of the target audience, I'm especially excited!
Speaker : Noson Yanofksy
Date : May 7 @ 2pm
Title : Theoretical Computer Science for the Working Category Theorist
Where : Zoom 929-1640-9872
Abstract:
This talk is a preview of a forthcoming book in the Applied Category Theory series of Cambridge University Press. The book uses basic category theory to describe all the central concepts and prove 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. We will meet some of the deepest ideas and theorems of modern computers and mathematics, e.g., 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. I will report on new things I learned about theoretical computer science and category theory while working on this project.
as always, these details can be found at mdcats.github.io
Joshua Meyers (Aug 24 2020 at 21:50):I just watched this finally, very interesting! (if you want to watch, here is the video.) This is very relevant to me right now, as this semester I am taking a course in the theory of computing as well as a reading course in category theory.
Some thoughts/questions for now for @Noson S. Yanofsky or whoever else wants to chime in:
Turing machines (@14.53), as well as Register machines (@20.44) and circuits (@21.08) are said to form bicategories. What are the 2-cells?
Is there a way to give a general definition of "computing machine" which embraces Turing machines, Register machines, and circuits, in terms of the structures they must comprise and the functors to and from CompFunc and TotCompFunc they must partake in?
@40.43 Functions are defined sending computable functions to a measure of their complexity. It seems that you could also define more fundamental functions which send algorithms to a measure of their complexity; then the (time or space) complexity of a function could be defined as the minimum (time or space) complexity of any algorithm which implements the function. The situation could occur (a priori, it probably does a posteriori but I don't know enough CS to say for sure) that, given a function, it is impossible to simultaneously minimize both time and space complexity when choosing algorithms which implement the function. So by thinking in terms of the more fundamental functions, on algorithms, you can get a fuller picture of the relationship between time and space complexity.
@57.55 Professor Yanofsky wonders what structure "hard" functions have in the context of cryptography, and are they closed under composition, etc. I would say that "easy" functions are a subcategory of the category of all functions, and hard functions are just the complement of "Easy" in the category of functions, i.e. Hard Func Easy. So in particular, it doesn't seem to me that Hard is closed under composition, since I could imagine a Hard involution; then the composition of it with itself is the identity, which is clearly Easy.
Great talk! I'm really looking forward to the book coming out.