Basic Computer Science
Wednesday, July 29, 2009
Add Comment
Theoretical Computer Science has its roots in mathematics, where there was a lot of discussion of logic. It began with Pascal and Babbage in the 1800's. Pascal and Babbage eventually tried to come up with computing machines that would help in calculating arithmetic. Some of them actually worked, but they were mechanical machines built on physics, without a real theoretical background.
Another person in the 1800's was a man named George Boole, who tried to formulate a mathematical form of logic. This was eventually called Boolean Logic in his honor, and we still use it today to form the heart of all computer hardware. All those transistors and things you see on a circuit board are really just physical representations of what George Boole came up with.
Computer Science, however, hit the golden age with John von Neumann and Alan Turing in the 1900's. Von Neumann formulated the theoretical form of computers that is still used today as the heart of all computer design: the separation of the CPU, the RAM, the BUS, etc. This is all known collectively as Von Neumann architecture.
Alan Turing, however, is famous for the theoretical part of Computer Science. He invented something called the Universal Turing Machine, which told us exactly what could and could not be computed using the standard computer architecture of today. This formed the basis of Theoretical Computer Science.
Ever since Turing formulated this extraordinary concept, Computer Science has been dedicated to answering one question: "Can we compute this?" This question is known as computability, and it is one of the core disciplines in Computer Science. Still, there are other forms of Computer Science, answering such related questions as "Can we compute thought?" This leads to fields like Artificial Intelligence.
Another person in the 1800's was a man named George Boole, who tried to formulate a mathematical form of logic. This was eventually called Boolean Logic in his honor, and we still use it today to form the heart of all computer hardware. All those transistors and things you see on a circuit board are really just physical representations of what George Boole came up with.
Computer Science, however, hit the golden age with John von Neumann and Alan Turing in the 1900's. Von Neumann formulated the theoretical form of computers that is still used today as the heart of all computer design: the separation of the CPU, the RAM, the BUS, etc. This is all known collectively as Von Neumann architecture.
Alan Turing, however, is famous for the theoretical part of Computer Science. He invented something called the Universal Turing Machine, which told us exactly what could and could not be computed using the standard computer architecture of today. This formed the basis of Theoretical Computer Science.
Ever since Turing formulated this extraordinary concept, Computer Science has been dedicated to answering one question: "Can we compute this?" This question is known as computability, and it is one of the core disciplines in Computer Science. Still, there are other forms of Computer Science, answering such related questions as "Can we compute thought?" This leads to fields like Artificial Intelligence.
Computer Science is all about getting things done, to find progressive solutions to our problems, to fill gaps in our knowledge. Sure, Computer Science may have some math, but it is different from math. In the end, Computer Science is about exploring the limitations of humans, of expanding our horizons.
Let's look at some of the other consequences. In particular, what if we decided we wanted to write a program that would test what happens when we run a program on itself as input. For instance, the *nix program cat, when run on itself, would output the binary executable file. Some programs might never halt when run on themselves, though -- so let's use DOES-HALT to write pseudo-code for a program that checks to see what happens when a program is given itself as input. let's call it SELF-HALT, and SELF-HALT will halt if the input program would *not* halt on itself.
SELF-HALT(program)
{
if(DOES-HALT(program, program))
infinite loop
else
halt
}
This code is pretty straight forward: if the program would halt on itself, then SELF-HALT goes into an infinite loop. Otherwise, it halts.In fact, the above argument is essentially a proof that the halting problem, as it is termed, cannot be solved in the general case. No DOES-HALT program exists. If it did, we would be able to generate contradictions such as the above -- a program that halts when it should loop forever, and that loops forever when it halts. Read More
Let's look at some of the other consequences. In particular, what if we decided we wanted to write a program that would test what happens when we run a program on itself as input. For instance, the *nix program cat, when run on itself, would output the binary executable file. Some programs might never halt when run on themselves, though -- so let's use DOES-HALT to write pseudo-code for a program that checks to see what happens when a program is given itself as input. let's call it SELF-HALT, and SELF-HALT will halt if the input program would *not* halt on itself.
SELF-HALT(program)
{
if(DOES-HALT(program, program))
infinite loop
else
halt
}
This code is pretty straight forward: if the program would halt on itself, then SELF-HALT goes into an infinite loop. Otherwise, it halts.In fact, the above argument is essentially a proof that the halting problem, as it is termed, cannot be solved in the general case. No DOES-HALT program exists. If it did, we would be able to generate contradictions such as the above -- a program that halts when it should loop forever, and that loops forever when it halts. Read More
"If it's there and you can see it — it's real.
If it's not there and you can see it — it's virtual.
If it's there and you can't see it — it's transparent.
If it's not there and you can't see it — you erased it !"
(anonymous)
0 Response to "Basic Computer Science"
Post a Comment