Before we write a single line of code, a deeper question exists: what problems are even possible for computers to solve? And for the solvable ones, what does it cost in time and memory?

This is the world of theoretical computer science. It's less about building specific apps and more about understanding the fundamental rules and limits of computation itself. Think of it as the physics that governs the digital universe. It explores the 'what' and 'why' before programmers tackle the 'how'.

It provides the mathematical backbone for all of computer science, from designing efficient algorithms to securing data on the internet. It helps us answer big questions, like whether a problem is solvable at all or if there's a fundamentally better way to approach it.

The roots of modern computing stretch back to the 1930s, a time before physical computers existed. Mathematicians and logicians were grappling with the very definition of 'computation'.

Alan Turing, a brilliant British mathematician, was a central figure. He imagined an abstract machine that could perform any conceivable calculation, provided it could be broken down into simple steps. This concept, now known as a Turing machine, became the bedrock of computational theory. It's a simple model: a tape, a head that reads and writes symbols, and a set of rules.

Turing's work wasn't just a thought experiment. He proved that there are problems his machine could never solve, a groundbreaking idea known as uncomputability. The most famous example is the Halting Problem: determining whether an arbitrary computer program will finish running or continue forever.

At the same time, Alonzo Church, an American logician, developed a different formal system called the lambda calculus. It turned out that Church's system and Turing's machines were equivalent in power—they could solve the exact same set of problems. This powerful idea, that different models of computation can be equivalent, is known as the Church-Turing thesis.

A Turing machine is the most powerful model of computation we know, but it's not the only one. Simpler models exist that are useful for specific, limited tasks. These models form a hierarchy, each with different capabilities.

Imagine you need to verify if an email address has a valid format (like name@example.com). You don't need a supercomputer for that. A much simpler model can do the job.