>>11242469>These are pure maths with applications to CSYou can arbitrarily distinguish between theoretical computer science and pure mathematics by your own tastes, but the fact is
1) many departments have tight collab between TCS and math
2) many professors are jointly in both departments, both those with CS phd’s And math phd’s
3) the topics I listed are BY FAR studied more in the CS department. If you think CS researchers stay away from pure research...you don’t have much experience about what you’re talking about. I think as recently as a few years ago Cook of all people had a paper on the complexity of operator analysis in Type-2 Effectivity. I know several papers that end up being about pure number theory. TCS research is by in large not motivated by “applications.”
>Unironically interested in knowing what you mean by thisThe biggest things that are fundamentally discrete about computation is state control / steps, since we are interested in algorithms that can terminate. However, the conventional Turing model has clear limitations as a logical / combinatorial structure, and there have been many other *reasonable* extensions to the machine that help us study more problems. Read more on “Complexity and Real Computation” by Blum, Shub, and Smale and then read Koiran’s weakening of the model, which makes it much more realizable. What you can’t escape in some sense (unless you claim you can make an oracle machine) is needing to examine the parts of a problem in order to make a decision - at no point can you really make a decision based on a global state in unit time or a unit step. And you can only really solve problems, which is evident in the Turing model, for whom the answer can be determined by only looking at these parts. This is a sort of elementary explanation, but Widgerson explains it better in his online book.
