#computation

Topics tagged "computation".

• Turing Machine

  An idealized machine of tape, head, and rules that defines exactly what it means for something to be computable.

• Finite Automaton

  A memoryless machine of states and transitions that recognizes exactly the regular languages.

• Church–Turing Thesis

  The claim that every reasonable model of computation can compute exactly the same functions as a Turing machine.

• Halting Problem

  The proof that no program can decide, for every program and input, whether it eventually halts or runs forever.

• Decidability

  The line between problems an algorithm can always settle and those no algorithm can settle at all.

• Big-O Notation

  A way to describe how an algorithm's cost grows with input size, keeping only the dominant term and ignoring constants.

• Complexity Class

  A grouping of problems by the computational resources — time or memory — needed to solve them.

• Computability & Complexity

  What a machine can compute in principle, and how much time and space it takes in practice — from the Turing machine to the million-dollar P versus NP question.

• P versus NP

  The open question of whether every problem whose solution is easy to check is also easy to solve.

• NP-Completeness

  The hardest problems in NP, all interreducible — solve one efficiently and you solve them all.