Skip to content Skip to sidebar Skip to footer

Basic Computer Science

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.

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. 

8 comments for "Basic Computer Science"

  1. Αwesomе websіte you have here but I was
    ωanting to know if you knew of any message boards that covег thе same topics discuѕsеd here?
    I'd really love to be a part of community where I can get opinions from other knowledgeable individuals that share the same interest. If you have any suggestions, please let me know. Bless you!

    My blog post: sonography schools in atlanta

    ReplyDelete
  2. Very nice post. I definitely love this site. Thanks!


    My web site ... /d5o2eki

    ReplyDelete
  3. I think the admin of this web page is really working hard in favor of
    his web site, as here every data is quality based information.



    Here is my blog post; An X-RayTechnician

    ReplyDelete
  4. I have learn some good stuff here. Certainly worth
    bookmarking for revisiting. I wonder how so much effort
    you place to create the sort of great informative website.


    Feel free to surf to my site ... Ralph Lauren

    ReplyDelete
  5. I am really impressed with your writing skills as well as
    with the layout on your blog. Is this a paid theme or did you modify
    it yourself? Either way keep up the excellent quality writing,
    it is rare to see a great blog like this one nowadays.


    My weblog: super bowl tickets **

    ReplyDelete
  6. Hi would you mind letting me know which hosting company
    you're using? I've loaded your blog in 3 different browsers and I must
    say this blog loads a lot quicker then most. Can
    you recommend a good web hosting provider at a reasonable price?
    Thanks a lot, I appreciate it!

    Review my page; tints of nature reviews - -

    ReplyDelete
  7. Your blog give many information thanks for share this informative article.
    access torrentHound in UK

    ReplyDelete