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)

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)

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)

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)

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)

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)

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)

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)

I dont really understand your answers. Let me please explain you what is obscure to me in them.

• First of all, my main objective was to challenge you on your point of view that computer science is delimited by a notion of mechanically computable (via the relativized P vs NP statement), and I do not see you reply to this challenge.
• Second, I do not understand your heartbeat example. Can I write a program that reasonably evaluates or tell if another one halts? Well I certainly can write a program that accepts this halting problem, though I cant decide it of course... But it seems to me this is exactly what your heartbeat trick does: accept a problem which can trivially be accepted, so of course your hardware interrupt does not seem like a miracle... Maybe I am missing something?
• Finally, you talk of the precious power to compute. Is this some source of inspiration to your mechanically computable approach to capture the essence of CS? Would be intersting! However, what makes you think energy is a resource so fundamentally different from the more classical time or space resources that it blows mathematics out of the water??? It seems to me that this last assertion pretty much lacks any justification. In fact, it seems to me pretty much untrue. The design of energy efficient algorithms is fairly common in modern research, and the mathematical language is often used as an analysis mainframe in this context.

My point of view is that CS is a fairly complete science, and like physics, the most theoretical apsects are quite abstract and not necessarily directly linked or linkable to physical reality. Perhaps this is even "worse" than in physics sometimes... However, this is not a determining criterium, just like mechanically computable is arbitrary if applied dogmatically: it implies that relativized statements are not part of CS whereas their non-relativized counterparts would be. --Powo 00:55, 3 December 2005 (UTC)

Should they remove the theory of Evolution from Biology? The "P=NP" is still a theory,

P=NP a theory? I dont thionk you understand what P=NP is, neither what a theory is. It is a statement, thats all. - P

Here you act like you don't understand but below you do: "The actual truth or not or unprovability of P=?NP". Of course, it is a statement. It lacks proof. You like to say "I don't think you understand." - D

and its answer will determine if it belongs in CS or TCS.

I wonder what this assertion could mean! - P

You need that explained also? Your viewpoint that is only of a scientific academic discipline has limited you, but I'm sure that wasn't the intention of the discipline. - D

You've asked me to apply a theory as if it was fact and a concrete factor to delimit CS from TCS.

Did I? The only thing I said was that $P=NP$ is more related to mechanical computations than its relativised equivalent.

About $P=NP$, you questioned: "...CS and mathematics have a non-empty intersection?" It is really a ambiguous question. The nondeterministic elements of the domain of P=NP are what make it not mechanical. Of course, random number generators are mechanical are mechanical. If I ask you as part of a method, however, to pick a number from 1 to 100, that would make P=NP not mechanical. Unless you want to declare youself as purely mechanical, then I understand your confusion. - D

You've implied that mechanistic explanation has a direct relationship with P=NP. Do you suggest that mechanistic explanation is theory?

I don think you understand what I meant. The actual truth or not or unprovability of P=?NP has nothing to do with it. Lets forget it since it confuses you. The only thing I did was to suggest that oracle machines are less mechanistic than standard TM's, at least from a physical point of view! - P

Did your professors ever look at your non-A tests and said: "Lets forget this subject, as it confuses you." What source of information did you use to think that oracle models are not mechanical? - D

I've already given an example of a computation that is not known to be mechanical -- conscious. The realm of the Turing Test covers a theory that it may or may not be mechanical. This is not to imply that any conscious object has similar random events that would fall under P or NP.

Gee, this is metaphysics. I am not interested in metaphysics, sorry. - P

CS isn't interested in mataphysics also -- just the mechanical stuff. That is why it doesn't include theoretical computer science in practice. You can cling on to your theoretical academic viewpoint as long as you want, but your employer probably will ask you to do something real. - D

In CS they are exceptions, and in TCS they are questions. What's probably obscure to this is CS as a science and CS as a disclipine. You ask me if something belong in CS, but you don't state if it questioned to belong in the science or in the discipline or both.

My POV is that CS is the scientific academic discipline. The rest is not CS. What is a computer scientist? A researcher! What is CS, the science developed by computer scientists. Simple no? Thus, TCS is a subset of CS.

OK. We've made it perfectly clear that you are only interested in the academic discipline and its program structure. There are, however, much greater viewpoints on CS that go well beyond that and it is all CS. From your deduction, we'll make *sure* that we'll tell Mr. Gates that his work doesn't belong in CS as curricula or as tools or even as an OS to study simply because he never graduated as a computer scientist. And, be *sure* to tell that to academia. This is another debate, unfortunately.- D

This article should be more about the mathematics of computation and what could be computed by any means.

I once was a mathematician, once was a theoretical computer scientis, and currently am a CS researcher. However, I do not know what the mathematics of comutation are. Could you please explain this to me? At the same time I will understand what is the mathematics in use by the computer you want to keep in the top lines of the definition of CS. - P

This is simple. Write a virtual machine. Have it compile, assemble, execute, and print the result of "1 + 1." - D

The "computation" article should be about systems that exist, its history and how it relates to different fields. It is easy to point out in computation the question of consciousness to lead to theory of computation.

Please keep metaphysics out of the article. Thank you. - P

If you are conscious and you believe conscious is metaphysics, please stay out of the article by your own request. Silly. - D

It is easy to point out questions of P=NP or other complexities in computation that lead to its theory of computation.

I cant understand this sentance. Is this english???

You went "there", again. - D

Some have said that CS is about "what" can be computed while math is about "how" it can be computed.

So now, you claim mathematics is about what can be computed? - P

No. See below. - D

I can tell you that in my very close friends, more than half a dozen are mathematicians (researchers). Only one of them, a logician, was aware of computability issues from outside our discussions. No, mathematics are not about computation at all... - P

Do read the next bit before you tell me what I claim.... -D

Understand, that is really a very general "rule of thumb" statement and it doesn't cover every aspect. You can put the "how" into CS, but you can't put the "what" into math. Anotherwords, you can program a computer to think on how to solve mathematics but you can't define a mathematical object to describe what can be computed.

Is this so??? So what in the world is a Turing Machine? What is complexity theory? What is the class of efficiently decidable problems? Obviously you have never heard of these! - D

That was rude, and I'm sure you can answer them and even research them. You like to complain and assume people are stupid? That is your intention when you state "you have never heard of these" even though we have discussed them? I've even cited sources for you. I've even quoted text right out of the sources. You've called those quotes incoherent and have wondered if they are even written in English. Wow. Again, the above statement about what can be computed was generalized. - D

However, the P=NP is obviously a step towards that intent.

Gee, you dont know what complexity theory is about! Its about efficently decidable problems. P=NP may be a step, but you've missed all the rest... -P

You decided on a abhorrently efficient level if you didn't even read what I wrote. I don't know why you want to challenge me. Challenge the sources. I didn't ask to be degraded by you. - D

About your last question of consumption, it isn't inspiration as it's just an obvious resource needed on applied science. It is one of those things that seperate pure CS and pure math from their application.

Obviously you are unaware that energy efficient algorithmics is a field of computer science with both theoretical aspects and applications. - P

Oh wait, you said "you've missed all the rest" but you do know about energy efficiency. I'm pretty sure your intention is more to degrade others than to improve an article. - D

The Mars rovers have to determine if there is enough power to get from point A to point B. They calculate approximate energy for all movement. If you have ever downloaded the program that evaluates the land and displays basic command sets, you'll see they work with lots of data. Sure, you could plug in a analysis mainframe somewhere else besides inside the bot and have them communicate. Is this analysis mainframe like consciousness?

What? You are asking if an analysis mainframe would have anything to do with consciousness??? Why would I have any answer to such questions. I am not interested in such questions. - P

Obviously, you avoided the question and even the asymmetrical analoguous points you seem unconscious about. - D

Why dont you let computer scientists define computer science? The CS page is in an awfull state. Would you want to define the physics page, the chemistry page, the biology page, etc? I would not, I stick to what I know. - Powo

Are we back to -- is this another Turing test? — Dzonatas 14:06, 3 December 2005 (UTC)

Why dont you let computer scientists define computer science? The CS page is in an awfull state. Would you want to define the physics page, the chemistry page, the biology page, etc? I would not, I stick to what I know. - Powo

Seriously, you've implied something. — Dzonatas 22:01, 3 December 2005 (UTC)