Theory Of Computation

Computability

This guide helps you get your bearings in Computability before you start exploring the interactive timeline, framework graph, and concept maps.

Before You Dive In

Computability studies the formal limits of computation, proof, and efficient solvability.
Rough timeline: automata and formal language foundations -> computability and undecidability -> complexity-theoretic stratification -> modern proof complexity and cryptographic hardness.
Start with models of computation and reductions; they provide a shared language for impossibility and efficiency results.
In Noosaga, compare frameworks by what they bound: computability, time, space, randomness, or proof size.

Turing machineCanonical abstract model used to define algorithmic computability.

DecidabilityWhether a problem has an algorithm that halts with a correct yes/no answer on all inputs.

Complexity classSet of problems grouped by resource-bounded solvability (e.g., P, NP, PSPACE).

ReductionTransformation showing one problem is at least as hard as another.

Lower boundProvable minimum resource requirement for solving a problem.

Equating unproven with easy; many central conjectures remain open for decades despite intense effort.

Assuming NP-complete means no practical algorithms for useful instances.

Confusing computability limits with engineering limits on current hardware.

Open the interactive view and scan the framework timeline. Which frameworks came first? Which ones overlap? Where are the big transitions?

Click into individual frameworks to read what each one claims, where it came from, and how it relates to its neighbors.

See how the key ideas within a framework connect. This is useful for figuring out what to learn first and what depends on what.

Take the quiz for any framework you've read about. It's a quick way to find out whether you actually understood the core ideas or just skimmed them.