Talk:Theory of computation/1

Hi all. The curent definition states that the theory of computation deals with wether and how efficiently problems can be solved by a computer. I have two observations:

- The theory of computing has more than complexity and computability. c.f.| theory of computation (ACM classification)

- The use of "solved by a computer" seems restrictive: the theory of computation deals with more than what can be computed by a computer, no? It depends on what a computer is of course. If its a digital computer, then the definition is very restrictive. If it's a TM, it is very restrictive too. I suppose this is implicit, that here a computer should be understood in a very broad sens, but that makes the definition ambiguous.

Best, --Powo 20:36, 30 November 2005 (UTC)[reply]

In his book Introduction to the Theory of Computation, Sipser also includes automata theory and formal languages, which should be discussed here as well. I don't think that analysis of algorithms and formal methods have a place here. I think that the ACM category F could better have been called theoretical computer science. I left a link on you talk to a discussion on if or how we should distinguis between computability theory and recursion theory (which deals with more general forms of computation). —R. Koot 00:13, 1 December 2005 (UTC)[reply]

The definition there is really just what I could come up with off the top of my head. It does have the advantage of, I think, being both succinct and saying at least most of what we'd like it to say. The distinction between all of theoretical computer science and the theory of computation is a pretty minor one, but it seems to me that, when using "theory of computation", most people refer to computability and complexity theory, and indeed perhaps the closely related automata theory, while "theoretical computer science" encompasses also (et alia) algorithms and formal methods. It would perhaps be an improvement to include some more discussion of automata, though I wanted to avoid overlap with Computability theory (computation) which already does include seom of that discussion. --Readams 07:03, 1 December 2005 (UTC)[reply]

I'm sure there will be continual debate on this definition and many other definition of aspects of computer science. One thing we can do and more easily agree upon is the distinctions between different aspects. As you noted above there is a distinction between theoretical computer science and the theory of computation. Simply worded, the theory of computation is like a portal between computer science and theoretical computer science. We can find the theory of computation in computer science and theoretical computer science, but the application and study of both are different enough to say they are distinct disclipines. I noticed the Theoretical computer science page doesn't exist at this time. Oh my, it's such a young science... theoretically. — Dzonatas 12:19, 2 December 2005 (UTC)[reply]

Doese your explanation of Theory of computation as a portal between Computer Science and Theoretical Computer Science means you consider the following inclusion to be false?

Theory of computation subset_of Theoretical computer science subset_of Computer Science

If you do, do you think your opinion is an NPOV? --Powo 18:54, 2 December 2005 (UTC)[reply]

I used the word portal to avoid subsets of an object. Theoretical computer science is the mathematics of computing and is not limited to the domain of computer science, which is limited by mechanical computability. Theoretical computer science isn't a subset of computer science in application, but it is as academic curricula. Some state that computer science is rooted in mathematics and others say it is rooted with physical sciences. It may be rooted that way as academic curricula, but that doesn't mean it is that way in reality. Academia must fund its programs somehow, and they often do attach newer programs to departments that already exist. I've seen Information Technology as its own department and Computer Science as a division of Science in the same college. — Dzonatas 20:57, 2 December 2005 (UTC)[reply]

Dear Dzonatas, could you please point me to sources where CS is rooted in physical sciences (what physical sciences)? This interests me pretty much, and I am unaware of this point of view. Although you know from our previous discussions that I do consider CS to be strongly linked to some physical reality. I do not follow you easily when you say that CS is limited by mechanical computability. What is mechanical computability? Is quantum computing mechanical computability? It sure is a candidate. An oracle Turing machine probably does not qualify as a mechanical computer from your point of view. Does the fact of taking such abstraction with respect to mechanical computation means this is not computer science anymore, but mathematics? If so, then maybe many modern physic theories could be removed from physics and added to mathematics too: e.g. holographic theory, cord theory, etc... They are mainly mathematical and their usefulness in terms of describing reality is hypothetical.

It seems to me that if you consider bounded by mechanical computability as the criteria, then $P=NP$ is a CS statement and $P^{A}=NP^{A}$ is not. This seems weird, and the only cure seems to be to remove theoretical computer science from CS altogether. Could theoretical computer science (TCS) not be seen as a subset of CS, but agree that CS and mathematics (mathematical logic in this case) have a non-empty intersection? Best regards, --Powo 21:26, 2 December 2005 (UTC)[reply]