Timeline for Is there a theory that combines category theory/abstract algebra and computational complexity?

5 events

when toggle format	what		by	license	comment
Jun 21, 2022 at 16:20	comment	added	Lukas Juhrich		@AntonFetisov this idea of calling subprograms – ignoring any notion of inputs being of a „correct“ or „incorrect type“ – might fit into the framework of operads.
Jul 30, 2018 at 23:42	comment	added	Martin Berger		@AntonFetisov Have you tried writing down the details? It's not pretty.
Jul 30, 2018 at 12:14	comment	added	Anton Fetisov		Obviously no all programs are composable in this way, which naturally leads us to a category of TMs. It's also likely that one should let go the notion of a time-space unlimited TM, which isn't practically feasible anyway. Is there some published notion which captures this structure?
Jul 30, 2018 at 12:13	comment	added	Anton Fetisov		I'd say that the composition of Turing machines is fairly clear when you think about them as abstract computer programs. The natural way to compose programs is to call one as a subprogram of another. More generally, each program is a computable in finite time and space function which accepts certain formatted input and outputs another formatted string, which can be fed into another function. It's possible that some garbage inputs will result in garbage outputs or that some function fails to execute in the allotted time and space, in which case the whole program crashes.
Jul 22, 2015 at 12:08	history	answered	Martin Berger	CC BY-SA 3.0