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]