Difficulty: Introductory | Prerequisites: None. This is foundational material for any CS programme.
This topic sits right at the start of a CS degree and asks a deceptively simple question: what kind of discipline is computer science? Is it a science, an engineering field, or a branch of mathematics? The answer matters because it shapes how we evaluate programs, how we teach the subject, and what counts as valid knowledge in the field. You do not need prior CS coursework for this material, but it helps to know that CS has both theoretical and applied sides. If you have ever wondered why your degree requires both maths courses and lab-style projects, this is the explanation.
Computer science can be viewed through three lenses: as a science (empirical testing of systems), as engineering (building reliable computational artefacts), or as mathematics (deductive reasoning about formal objects). Scholars disagree on which lens is primary, and the field spans everything from pure theory of computation to practical software engineering. The foundational question of theoretical CS is "What can be automated?" and key unsolved problems like P = NP sit at its centre.
Empirical science
A discipline that gains knowledge through observation and experiment. In simple terms, you learn by building things, running them, and measuring what happens.
Computability theory
The branch of theoretical CS that asks which problems can be solved by a computer at all, using formal models of computation (e.g. Turing machines). Think of it as: "Can a computer ever solve this, even with unlimited time?"
Computational complexity theory
The study of how much time and memory different problems require to solve. Think of it as: "Even if a computer can solve it, how expensive is the solution?"
P = NP problem
One of the most famous unsolved problems in mathematics and CS. It asks whether every problem whose solution can be quickly verified can also be quickly solved. This is a Millennium Prize Problem, worth $1 million for a proof.
Paradigm (in CS classification)
A broad framework or worldview for understanding what computer science is. Scholars have proposed three main paradigms: the positivist (mathematical), the technocratic (engineering), and the scientific (empirical).
Deductive reasoning
Reasoning from general principles to specific conclusions, as in mathematical proof. In simple terms, you start with axioms and rules and prove that something must be true.
Formal methods / formal semantics
Mathematical techniques for specifying and verifying that software behaves correctly. Think of it as: treating a program like a mathematical theorem and proving it works.
CSAB (Computing Sciences Accreditation Board)
The body (comprising ACM and IEEE Computer Society representatives) that defines the core areas of computer science for accreditation purposes.
Every new machine that is built is, in a sense, an experiment. Constructing a system poses a question to nature, and we observe the answer by running the system and measuring its behaviour.
CS uses empirical testing to assess correctness of programs, much like other empirical disciplines.
The difficulty: unlike physics or chemistry, CS has struggled to define universal laws or theorems. The nature of experimentation in CS does not map neatly onto the traditional scientific method.
CS shares traits with astronomy, economics, and geology, where observation and experience do not always fit a strict experimental template.
Advocates say the reliability of computational systems is investigated the same way as bridges in civil engineering or aircraft in aerospace engineering: you build it, test it under stress, and verify it meets specifications.
A key distinction: empirical sciences observe what currently exists. CS, by contrast, is concerned with creating new phenomena and artefacts, things that did not exist before the designer built them.
No universal "laws of nature" have been discovered in CS in the way they have in physics. The field creates rather than discovers.
Programs are realisations of mathematical entities (algorithms, data structures, formal languages) that can be deductively reasoned about.
Edsger W. Dijkstra and Tony Hoare treated programs as mathematical statements and viewed formal semantics for programming languages as mathematical axiomatic systems.
Under this view, proving a program correct is analogous to proving a theorem.
Peter Wegner proposed three categories: science, engineering, and mathematics.
Peter Denning's working group framed them as: theory (hypothesis), abstraction (modelling), and design.
Amnon H. Eden described them as:
The positivist paradigm: treats CS as a branch of mathematics, dominant in theoretical CS, relies on deductive reasoning.
The technocratic paradigm: found in technology-oriented approaches, prominent in software engineering.
The scientific paradigm: approaches computational artefacts empirically, as a natural science would, identifiable in branches of artificial intelligence.
CSAB identifies four core areas essential to CS:
Theory of computation
Algorithms and data structures
Programming methodology and languages
Computer elements and architecture
Additional areas CSAB recognises: software engineering, artificial intelligence, computer networking and communication, database organisation, parallel computing, distributed computing, human-computer interaction, computer graphics, operating systems, and numerical/symbolic computation.
Mathematical and abstract at its core, but motivated by practical computing problems.
It aims to understand the fundamental nature of computation and, from that understanding, develop more effective methods and algorithms.
According to Peter Denning, the fundamental question underlying CS is: "What can be automated?"
Theory of computation addresses two central questions:
What can be computed? Computability theory examines which problems are solvable on various theoretical models of computation (e.g. Turing machines, lambda calculus). Some problems are provably unsolvable, no matter how powerful the computer.
What resources are required? Computational complexity theory studies the time and space costs of solving different classes of problems. Even if a problem is solvable in principle, it may require impractical amounts of time or memory.
One of the seven Millennium Prize Problems (Clay Mathematics Institute, $1 million prize).
P is the class of problems solvable in polynomial time. NP is the class of problems whose solutions can be verified in polynomial time.
The question: does P = NP? That is, if you can check an answer quickly, can you also find it quickly?
This remains one of the most important open problems in both CS and mathematics.
The classification debate is not purely academic. If CS is treated as engineering, accreditation and curriculum design emphasise testing, reliability, and design methodology. If it is treated as mathematics, the emphasis shifts to proof, formal methods, and theoretical foundations. Most modern CS programmes blend all three perspectives, which is why a typical degree includes discrete maths, algorithm analysis, lab projects, and software engineering courses.
Theory of computation underpins everyday technology. Complexity theory is the reason modern encryption works: the security of RSA, for instance, rests on the assumption that certain problems (like factoring large numbers) are computationally hard.
"Computer science is just programming." Programming is one activity within CS, but the discipline also encompasses theory, hardware architecture, formal methods, AI, and more. The source material makes clear that CS spans from pure mathematics to hands-on engineering.
"CS must be either a science or an engineering discipline, not both." The three-paradigm models (Wegner, Denning, Eden) all recognise that CS contains elements of science, engineering, and mathematics simultaneously. The debate is about emphasis, not exclusive categorisation.
"If a problem is computable, a computer can solve it efficiently." Computability and complexity are different questions. A problem can be theoretically solvable but require more time than the age of the universe for large inputs. That is exactly what complexity theory studies.
"P = NP has been solved." It has not. It remains open and is one of the seven Millennium Prize Problems.
⚠️ Know the three paradigms by name and by scholar: Wegner (science, engineering, maths), Denning (theory, abstraction, design), Eden (positivist, technocratic, scientific). Expect a matching question.
⚠️ Be able to explain the difference between computability and complexity. Computability asks "can it be solved at all?" Complexity asks "how much does it cost to solve?"
⚠️ Know what P and NP stand for and what the P = NP question asks. This appears in nearly every intro CS theory exam.
⚠️ Be able to name the four core CSAB areas: theory of computation, algorithms and data structures, programming methodology and languages, computer elements and architecture.
⚠️ Understand why CS is described as empirical: building and running a system is a form of experiment, even if it does not follow the traditional lab-science method exactly.
True or False: Computer science is universally classified as a branch of mathematics. (False. It is debated across three paradigms: science, engineering, and mathematics.)
Fill in the blank: Computability theory asks which problems are ______ on theoretical models of computation. (solvable)
True or False: Computational complexity theory is concerned with whether a problem can be solved at all. (False. It is concerned with how much time and space a solution requires.)
Fill in the blank: The P = NP problem is one of the seven ______ Prize Problems. (Millennium)
True or False: According to the engineering view, CS discovers laws of nature. (False. The engineering view holds that CS creates phenomena rather than discovering natural laws.)
Q: Name and briefly describe the three paradigms of computer science as identified by Amnon H. Eden.
A: The positivist paradigm treats CS as a branch of mathematics and relies on deductive reasoning. The technocratic paradigm views CS through the lens of engineering and technology, prominent in software engineering. The scientific paradigm approaches computational artefacts empirically, as a natural science would.
Q: What is the fundamental question underlying computer science, according to Peter Denning?
A: "What can be automated?"
Q: Explain the difference between computability theory and computational complexity theory.
A: Computability theory asks which problems can be solved at all by a computer (on any theoretical model of computation). Computational complexity theory asks how much time and space (memory) are needed to solve those problems.
Q: What are the four core areas of computer science identified by CSAB?
A: Theory of computation, algorithms and data structures, programming methodology and languages, and computer elements and architecture.
Q: Why do proponents of the engineering view argue that CS is not a traditional empirical science?
A: They argue that empirical sciences observe what already exists in nature and discover laws, while CS is concerned with creating new artefacts and phenomena. No universal natural laws have been found in CS.
Q: What is the P = NP problem, and why is it significant?
A: It asks whether every problem whose solution can be verified in polynomial time (NP) can also be solved in polynomial time (P). It is one of the seven Millennium Prize Problems and remains unsolved. Its resolution would have major implications for cryptography, optimisation, and many other fields.
This material connects directly to discrete mathematics and algorithm analysis, where you will use the theoretical frameworks introduced here (computability, complexity classes) in a more rigorous way. It also links to software engineering courses, which embody the "technocratic paradigm" through design patterns, testing methodology, and system reliability. If your programme includes a course on formal methods or programming language theory, that is the mathematics paradigm in action, building on Dijkstra and Hoare's view of programs as mathematical objects.
Computer science as a discipline, CS 101, nature of computer science, empirical discipline, is CS a science, CS paradigms, positivist paradigm, technocratic paradigm, scientific paradigm, Peter Wegner CS, Peter Denning CS, Amnon Eden CS, Dijkstra formal methods, Tony Hoare, computability theory, computational complexity, P vs NP, P equals NP, Millennium Prize Problems, CSAB, ACM, IEEE Computer Society, theory of computation, algorithms and data structures, programming methodology, computer architecture, software engineering, artificial intelligence, theoretical computer science, formal semantics, deductive reasoning in CS, what can be automated