Acesso mais rápido do que o navegador!
9 relações: David Stifler Johnson, Emil Post, Entscheidungsproblem, Histórico de computação, Máquina de Turing, Michael Sipser, NP-completo, Problema da parada, Problema de decisão.
David Stifler Johnson
David Stifler Johnson (9 de dezembro de 1945 – 8 de março de 2016) foi um cientista da computação estadunidense especializado em algoritmos e otimização.
Novo!!: Problema da correspondência de Post e David Stifler Johnson · Veja mais »
Emil Post
Emil Leon Post (Augustów, Polônia do Congresso, no Império Russo (atual Polônia), 11 de fevereiro de 1897 – Nova York, Estados Unidos, 21 de abril de 1954) foi um matemático polonês-estadunidense.
Novo!!: Problema da correspondência de Post e Emil Post · Veja mais »
Entscheidungsproblem
O Entscheidungsproblem (termo alemão para "problema de decisão") é um problema da lógica simbólica que consiste em achar um algoritmo genérico para determinar se um dado enunciado da lógica de primeira ordem pode ser provado.
Novo!!: Problema da correspondência de Post e Entscheidungsproblem · Veja mais »
Histórico de computação
Na ciência da computação, um histórico de computação é um conjunto de passos tomados por um Autômato enquanto computa seu resultado.
Novo!!: Problema da correspondência de Post e Histórico de computação · 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!!: Problema da correspondência de Post e Máquina de Turing · Veja mais »
Michael Sipser
Michael Fredric Sipser é um professor de Matemática Aplicada no grupo de teoria da computação do Massachusetts Institute of Technology.
Novo!!: Problema da correspondência de Post e Michael Sipser · Veja mais »
NP-completo
Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo.
Novo!!: Problema da correspondência de Post e NP-completo · Veja mais »
Problema da parada
Na teoria da computabilidade o experimento mental do problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir.
Novo!!: Problema da correspondência de Post e Problema da parada · 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!!: Problema da correspondência de Post e Problema de decisão · Veja mais »
