What Can a Machine Compute, and at What Cost?

Computer science covers an enormous range. It runs from the logic gates inside a processor to the protocols that carry traffic across continents, and each stretch of that range brings its own vocabulary: registers and instruction sets, pointers and hash functions, packets and ports, keys and certificates. Faced with that spread, it is natural to treat the subject as a series of technologies, each learned on its own terms.

A more durable way in starts with one observation. Every topic in computing is a question about computation: what it is, what it costs, how its data is represented, and what happens when someone tries to subvert it. Languages change and hardware turns over within a decade; those questions stay fixed.

Read in this light, the major ideas of the field become parts of a single account. Rules define what a machine can do. Layers of abstraction make those rules usable at scale. Growth rates decide what is feasible, and proofs mark where feasibility ends. Representation decides how faithfully a computation models the world, and adversarial thinking decides whether it survives contact with an attacker. Each step follows from the last.

Computation belongs to the rules

A Turing machine has an unbounded tape, a read-write head and a finite table of rules. Nothing about it depends on electricity or silicon. The Church-Turing thesis holds that any procedure that can be carried out systematically, step by step, can be carried out by such a machine, and every alternative model of computation proposed so far has proved equivalent in what it can compute.

The consequence is substrate independence: computation is a property of the rules followed, independent of the material that follows them. Software describes a computation, and hardware is one way of carrying it out. The stored-program computer makes this practical. With instructions held in the same memory as data, a program becomes data that a single universal machine can load and run, which is why a program written on one machine can run on another of entirely different design, given a compiler or interpreter for it.

Interfaces make the rules usable

A universal machine executing simple rules one at a time is powerful in principle and unwieldy in practice. What turns it into something people can build on is abstraction: each layer of a system hides its implementation behind an interface. Transistors become logic gates, gates become an instruction set, instructions support an operating system, and the operating system offers files, processes and network connections to applications.

An interface works as a contract. Code that depends only on the contract keeps working when the implementation behind it is rewritten, optimised or moved to new hardware, and separate teams can build separate layers in parallel. Every abstraction also leaks under some conditions. Memory presented as one flat array of equal-cost locations reveals its cache hierarchy the moment a program steps through data in an awkward order, and the program slows sharply. Skilled engineers work through the interface while keeping a clear picture of where its hidden details are likely to surface.

Growth rate decides what is feasible

Once a computation can be expressed, the next question is what it costs. Big-O notation captures how an algorithm's time or memory grows with the size of its input, and that growth rate belongs to the algorithm itself. Doubling processor speed lets an O(n²) algorithm handle an input only about 1.41 times larger in the same time. For an O(2ⁿ) algorithm, the same upgrade adds a single item.

This is why the choice of algorithm dominates at scale. Moving from an O(n²) sort to an O(n log n) sort on ten million items cuts the work by a factor of several hundred thousand, before constant factors are considered, a gain far beyond any hardware generation. Cost also depends on how data is held. An array offers constant-time access by position; a hash table offers constant average-time lookup by key; a balanced tree offers logarithmic search while keeping its contents in order. The operations that need to be fast select the structure, and the structure determines which algorithms are available and what they cost.

Some limits hold on every machine

Growth rates describe what is expensive. A deeper result describes what lies beyond reach altogether. Turing proved that no single algorithm can decide, for every program and every input, whether that program eventually halts. Suppose such a decider existed: a program could consult it about its own behaviour and then do the opposite, which yields a contradiction. The halting problem is undecidable, and the proof holds for every machine that will ever be built, however fast. Individual programs can still be analysed; the limit applies to a general method covering all of them.

Between the decidable and the practical lies a second boundary. Problems in P can be solved in polynomial time; problems in NP have solutions that can be checked in polynomial time. NP-complete problems, such as deciding whether a map has a route through every city within a given total distance, have no known polynomial-time algorithm, and whether one exists remains the open P versus NP question. Two different conditions are therefore in play: decidability asks whether any algorithm exists at all, and tractability asks whether one exists that scales. Practitioners meet intractable problems with approximation algorithms, heuristics and restricted inputs, and modern cryptography turns assumed hardness into protection.

Every encoding models the world at a price

Everything a computer processes passes through a finite pattern of bits, so every value is a model with a systematic gap from the thing it represents. Floating-point arithmetic stores most decimal fractions approximately, which is why 0.1 + 0.2 evaluates to 0.30000000000000004 in most languages. A fixed-width integer has a largest value and, in many languages, wraps around when it overflows. ASCII's 128 characters were designed for English; Unicode extends coverage to the world's writing systems. Lossy compression discards detail permanently.

Each of these choices includes some information and excludes the rest by design. The productive habit is to ask of any encoding what it can express and where it diverges from its domain, because every result computed downstream inherits that gap.

Trust is a design property

The final element brings in the environment. Networks let computations cooperate across incompatible hardware because communication is layered: IP routes independent packets, TCP adds reliable ordered delivery, and each protocol functions as a contract between the parties that use it. Those same connections expose every system to an adversary who adapts to defences and searches for unexpected paths.

Security engineering therefore starts with a threat model that names the assets, the likely attackers and the attack surfaces before the first design decision. Encryption protects data, authentication establishes identity, least privilege limits what any compromised component can reach, and defence in depth keeps a single failure contained. Security emerges from the architecture, so it is specified alongside the architecture from the outset.

A framework in five questions

The argument compresses into a sequence that applies to any computational system. What is the computational model? What is the complexity class, and is the problem tractable at the required scale? Which data structure fits the operations that must be fast? Where will the representation diverge from the domain? Where are the trust boundaries, and has adversarial behaviour been modelled?

Asked in order, the questions turn an unfamiliar system into a structured analysis, and each answer constrains the next. They also guard against three recurring distortions: expecting faster hardware to rescue a poor growth rate, reading digital data as a neutral copy of the world, and treating security as a late addition. Computer science, seen through that lens, becomes the study of what can be computed, at what cost, and under what conditions, with every language, device and protocol finding its place inside one connected account.