Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is the Fundamental Theorem of Computer Science?

  1. Jan 16, 2010 #1
    What is the Fundamental Theorem of Computer Science?

    No such formally named theorem exists if I do a google search. But I'm very curious as to what students and professors of Computer Science might think it should be.

  2. jcsd
  3. Jan 16, 2010 #2
  4. Jan 17, 2010 #3
    Thanks story645, you've put some thought into this. And I'm suprised by your response.

    I was uncertain as to what to ask, and still am--as far as category: should it be computer science, information theory, information processing, and belatedly information science. I'll look over your links
  5. Jan 17, 2010 #4
    That has to be Lubarsky's Law of Cybernetic Entomology (which itself is a consequence of Murphy's Sixth Law), and its two corollaries.
  6. Jan 17, 2010 #5
    They're all sort of different fields, with the latter three sort of being subsets of the first and connected to each other. Information theory has it's own big theorems, one of them having to do with thermodynamic entropy.
  7. Jan 17, 2010 #6
    One day I'll have to pick-up information theory again.

    In studying artificial neuro-networks, I asked what is in common between digital processing and processing by ANNs? --and perhaps biological processing as well? The one common attribute I could discover is that they both rely on sigmoid transfer functions.

    In a software implementation of ANN's, the inputs to a gate are first summed than passed to a nonlinear transfer function such as arctan. In hardware, a saturation characteristics of an amplifier can be used.

    In digital processing the reliance on sigmoid transfer functions is not so obvious. But without it, the state of ones and zeros would ultimately become mixed by noise. I don't believe one could implement a two input gate without saturation conditions.

    Quantum computers are another matter. They may not fit into the scheme.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook