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]

There are classes, like discrete mathematics, that are redone just for CS/IT. They took out all the prerequisites of higher math and only required algebra, instead. The proofs were simplified to emphasize form over the ability to calculate/compute every possibility. It was successful pilot that became normal curricula. The significant point of this is that mathematics is a learning discipline; anotherwords, it's a language. Just because we can explain something in the language of mathematics doesn't make it rooted in mathematics. Just like just because we can explain something in English doesn't make it rooted in English, or we would have many English professors with claims to computation because they make people do input and output -- read and write. The Turing machine was well understood because it was described in the language of mathematics.

There are a few books. One I remember is "When computers were people." I have to find the titles of the others. They describe the computers, that were people, that computed simulations of physics for proof-of-concepts, for instance, like the stableness of a bridge. Those people needed to know math to follow the methods, but the process was more significant than the math. I'm sure that every basic instruction followed involved mathematics.

Today, we can write an entire computer program that doesn't do any bit of mathematics. Those kind of programs just control hardware.

I've seen some try to say that mechanical and chemical changes are different. In certain contexts, that is true. Quantum computers are generally considered done by chemical changes. In a chemical sense, a pure quantum computer, theoretically, has no physical force. However, mechanics also involve physical bodies and that includes quantum mechanics and, thus, quantum computers.

Oracles aren't miracles. Hardware interrupts are oracles in model sense. To the extent they are wanted as to tell if a program can effectively execute given only so much "tape" or it never halts gets into theory (i.e. "complexity theory"). Can you invent a program that reasonably evaluates another program to tell if it halts? Well, I suggest that the better method is to make active computer programs produce a heartbeat, and when there is no heartbeat we can suspend the program and have the process return a "halted" event or error. An oracle in this sense would listen for the heartbeats and would tell when it misses one. That wouldn't waste precious power to compute if a programs halts. That power consumption matters if you have solar power as your only source like the Mars explorers. Rooted in mathematics? Oh, that "power" thing, so to speak, blows mathematics out of the water. "How much energy is left... not enough to comp@^^@%^##" — Dzonatas 22:32, 2 December 2005 (UTC)[reply]