Is theoretical computer science on topic?

Question

This question was closed for being off topic, and then reopened, presumably for being on topic.

It seems to me that parts of theoretical CS are definitely on topic - e.g. I have read some analysis of algorithms in my number theory books. But do we want to consider questions about Turing Machines, Computability, etc on topic?

My initial thought is yes, as long as we don't start writing code. Something like lambda calculus seems on topic, and computability and algorithms show up on the list of Hilbert's problems. On the other hand, I could also understand the argument that CS has developed into its own domain. The Area 51 TCS proposal is working its way through commitment, though certainly having a SE dedicated to a topic doesn't mean that we can't discuss it here.

In my mind, this is similar to the question of whether we consider statistics to be part of mathematics or its own discipline.

At any rate, I'd like to hear the community consensus lest I start posting off-topic questions.

Answer 1

I think such questions are fine as long as they're about the parts of CS that are math. I think this particular question is on topic (though I don't actually think it's a good question, it's too vague and subjective).

Answer 2

The fact that there is an Area 51 proposal for TCS shouldn't mean it can't be discussed here. TCS is essentially mathematics, and there are likely to be a lot of theoretical computer scientists hanging around here as well. Computability theory is highly connected to logic, for instance; a lot of us here would probably be interested in that sort of thing. The solution to Hilbert's tenth problem shows that it is also connected to number theory.

My guess is that specific questions ("Does anyone see a way to improve this algorithm?") would be better off on the other site (once it does become operational, which may take some time), while more general ones ("Intuition for the proof that NL=coNL," "Conditions under which BPP=P") should be welcome here.

Answer 3

The Theoretical Computer Science site is for research-level questions in theoretical computer science.

There is a proposed Computer Science site which would cover theoretical and applied computer science at all levels.

While some areas of theoretical computer science are mathematical in nature, and therefore on-topic on this site, my personal preference goes for a site that can cover both the maths and the more applied aspects.