What is the Fundamental Theorem of Computer Science?

[Phrak]

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.

Anyone?

 

[story645]

Most intro to theoretical comp sci courses cover the standard basic problems:
Turing Completeness
P vs. NP
Halting Problem
Turing Test

Turing completeness is probably the closest to a fundamental theory.

 

[Phrak]

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

 

[hamster143]

That has to be Lubarsky's Law of Cybernetic Entomology (which itself is a consequence of Murphy's Sixth Law), and its two corollaries.

 

[story645]

should it be computer science, information theory, information processing, and belatedly information science

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.

 

[Phrak]

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.

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.