Jump to content

Talk:Theory of computation/1

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
< Talk:Theory of computation
This is an old revision of this page, as edited by Readams (talk | contribs) at 07:03, 1 December 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Theory_of_computation/1&oldid=29781620"