# Theory of computation

**computational theoristcomputational theorycomputation theorytheory of algorithmscomputationcomputer sciencesComputer theoryTheoryComputing Theoryfoundations of computation**

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.wikipedia

184 Related Articles

### Theoretical computer science

**theoretical computer scientisttheoreticalcomputer science**

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

of computing and includes the theory of computation.

### Automata theory

**automataautomatonautomata theories**

The field is divided into three major branches: automata theory and languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

Automata play a major role in theory of computation, compiler construction, artificial intelligence, parsing and formal verification.

### Alan Turing

**TuringAlan M. TuringAlan Mathison Turing**

Some pioneers of the theory of computation were Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann and Claude Shannon.

To this day, Turing machines are a central object of study in theory of computation.

### Pushdown automaton

**pushdown automataNondeterministic pushdown automatonPush-Down Automaton**

Non-deterministic pushdown automata are another formalism equivalent to context-free grammars.

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.

### Mathematics

**mathematicalmathmathematician**

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

### Computability theory

**recursion theorycomputablecomputability**

The field is divided into three major branches: automata theory and languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

### Computer science

**computer scientistcomputer sciencescomputer scientists**

Perhaps the most important open problem in all of computer science is the question of whether a certain broad class of problems denoted NP can be solved efficiently.

A computer scientist studies the theory of computation and the practice of designing software systems.

### Turing machine

**deterministic Turing machineTuring machinesuniversal computer**

There are several models in use, but the most commonly examined is the Turing machine.

Today, the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating questions in the theory of computation.

### P versus NP problem

**P = NPP ≠ NPP=NP**

This is discussed further at Complexity classes P and NP, and P versus NP problem is one of the seven Millennium Prize Problems stated by the Clay Mathematics Institute in 2000.

The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem.

### Algorithm

**algorithmsalgorithm designcomputer algorithm**

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

### Rózsa Péter

**Péter, RózsaPéterR. Politzer**

Some pioneers of the theory of computation were Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann and Claude Shannon.

Originally published in Hungarian, it was the second Hungarian mathematical book to be published in the Soviet Union because its subject matter was considered indispensable to the theory of computers.

### Ramon Llull

**Raymond LullRamon LullArs Magna**

Some pioneers of the theory of computation were Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann and Claude Shannon.

He is also considered a pioneer of computation theory, especially given his influence on Leibniz.

### Programming language

**programming languageslanguagedialect**

Regular expressions, for example, specify string patterns in many contexts, from office productivity software to programming languages.

### John Hopcroft

**HopcroftJohn E. HopcroftJohn Edward Hopcroft**

His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields.

### Jeffrey Ullman

**Jeffrey D. UllmanUllmanJeff Ullman**

His textbooks on compilers (various editions are popularly known as the Dragon Book), theory of computation (also known as the Cinderella book), data structures, and databases are regarded as standards in their fields.

### Turing Award

**ACM Turing AwardA.M. Turing AwardA. M. Turing Award**

The Official Problem Description was given by Turing Award winner Stephen Cook.

### Finite-state machine

**finite state machinestate machinefinite automata**

Another formalism mathematically equivalent to regular expressions, Finite automata are used in circuit design and in some kinds of problem-solving.

Finite state machines are a class of automata studied in automata theory and the theory of computation.

### Introduction to Automata Theory, Languages, and Computation

**Cinderella bookformal languages**

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation.

### Massachusetts Institute of Technology

**MITM.I.T.Massachusetts Institute of Technology (MIT)**

### Model of computation

**models of computationmodelmodels of computing**

### Computational complexity theory

**computational complexitycomplexity theorycomplexity**

The field is divided into three major branches: automata theory and languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

### Church–Turing thesis

**Church-Turing thesisChurch's thesisTuring's Thesis**

Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation (see Church–Turing thesis).

### Decidability (logic)

**decidabledecidabilityundecidable**

It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any decidable problem solved by a Turing machine will always require only a finite amount of memory.

### Mathematical logic

**formal logicsymbolic logiclogic**

Therefore, mathematics and logic are used.

### Alonzo Church

**ChurchChurch, Alonzo**