computation - Concepts

Explore concepts tagged with "computation"

Total concepts: 12

Concepts

Undecidability - The property of a decision problem for which no algorithm can exist that always gives a correct answer for every possible input.
Turing Machine - A theoretical mathematical model of computation that defines an abstract machine manipulating symbols on a tape according to rules, forming the foundation of computer science.
Halting Problem - The proven impossibility of creating a general algorithm that can determine whether any given program will eventually halt or run forever.
Deterministic Finite Automaton - A finite-state machine in which each state has exactly one transition per input symbol, with no ambiguity and no epsilon moves.
Lambda Calculus - A formal system introduced by Alonzo Church for expressing computation through function abstraction and application, equivalent in power to Turing machines and foundational to functional programming.
Decidability - The question of whether a decision problem admits an algorithm that always halts and returns a correct yes-or-no answer, distinguishing decidable problems from undecidable ones.
Automata Theory - The study of abstract computing machines such as finite automata, pushdown automata, and Turing machines, and the classes of problems each type of machine can solve.
Computability Theory - The branch of mathematical logic and computer science studying which problems can be solved algorithmically and which are fundamentally unsolvable.
Computability - The study of which problems can in principle be solved by an algorithm or effective procedure, and which cannot, regardless of available time or memory.
Universal Turing Machine - A Turing machine that can simulate any other Turing machine when given a description of that machine and its input, providing the theoretical basis for the stored-program computer.
Church-Turing Thesis - The hypothesis that any function computable by an effective procedure can be computed by a Turing machine, defining the fundamental limits of computation.
Finite-State Machine - A computational model with a finite number of states, transitions between them triggered by inputs, and at most one active state at a time.

← Back to all concepts