Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Livre
Acesso mais rápido do que o navegador!
E sem anúncios!

R (complexidade)

Na teoria da complexidade computacional, R é a classe de problemas de decisão solúveis por uma máquina de Turing, que é o conjunto de todas as linguagens recursivas.

6 relações: Complexidade computacional, Função computável, Linguagem recursiva, Máquina de estados finita, Máquina de Turing, Problema de decisão.

Complexidade computacional

A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si.

Novo!!: R (complexidade) e Complexidade computacional · Veja mais »

Função computável

Funções computáveis são os objetos básicos de estudo na teoria da computabilidade.

Novo!!: R (complexidade) e Função computável · Veja mais »

Linguagem recursiva

A linguagem recursiva em matemática, lógica e ciências da computação, uma linguagem formal (a definir de seqüências finitas de símbolos tomados de um fixo alfabeto) é chamada recursiva se é um subconjunto recursivo no conjunto de todas as palavras possíveis sobre o alfabeto da linguagem.

Novo!!: R (complexidade) e Linguagem recursiva · Veja mais »

Máquina de estados finita

Uma máquina de estados finita (FSM - do inglês Finite State Machine) ou autômato finito é um modelo matemático usado para representar programas de computadores ou circuitos lógicos.

Novo!!: R (complexidade) e Máquina de estados finita · Veja mais »

Máquina de Turing

Representação artística de uma máquina de Turing A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).

Novo!!: R (complexidade) e Máquina de Turing · Veja mais »

Problema de decisão

Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.

Novo!!: R (complexidade) e Problema de decisão · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »