Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

R (complexity)

+ Save concept

In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages. [1]

6 relations: Computable function, Computational complexity theory, Decision problem, Finite-state machine, Recursive language, Turing machine.

Computable function

Computable functions are the basic objects of study in computability theory.

New!!: R (complexity) and Computable function · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: R (complexity) and Computational complexity theory · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: R (complexity) and Decision problem · See more »

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

New!!: R (complexity) and Finite-state machine · See more »

Recursive language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

New!!: R (complexity) and Recursive language · See more »

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: R (complexity) and Turing machine · See more »

Redirects here:

R (complexity class).


[1] https://en.wikipedia.org/wiki/R_(complexity)

Hey! We are on Facebook now! »