Teoria da computação: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m |
Etiquetas: Inserção de predefinição obsoleta Editor Visual |
||
Linha 1:
A '''teoria da computação''' é um subcampo da [[ciência da computação]] e [[matemática]] que busca determinar quais problemas podem ser computados em um dado modelo de computação. A computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função por meio de um [[algoritmo]]. Apesar de intuitivo na história humana, o conceito de execução de uma tarefa com passos finitos a fim de se obter um resultado, ou seja, um [[algoritmo]], não possuía uma definição formal até a conceituação do modelo de [[Máquina de Turing universal|Máquina Universal de Turing]].<ref name="Sipser-3rd">{{cite book|title=Introduction to the Theory of Computation 3rd|author=Michael Sipser|isbn=978-1-133-18779-0|year=2013|quote=central areas of the theory of computation: automata, computability, and complexity. (Page 1)|publisher=Cengage Learning|author-link=Michael Sipser}}</ref>▼
▲A '''teoria da computação''' é um subcampo da [[ciência da computação]] e [[matemática]] que busca determinar quais problemas podem ser computados em um dado modelo de computação. A computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função por meio de um [[algoritmo]]. Apesar de intuitivo na história humana, o conceito de execução de uma tarefa com passos finitos a fim de se obter um resultado, ou seja, um [[algoritmo]], não possuía uma definição formal até a conceituação do modelo de [[Máquina de Turing universal|Máquina Universal de Turing]].
A
Diversos modelos diferentes da computação foram propostos pelos primeiros pesquisadores. Um modelo, conhecido como [[Máquina de Turing]], propunha a construção de uma máquina universal, capaz de operar com uma sequência de instruções e dados entremeados em uma fita de comprimento infinito; a máquina poderia operar em um ponto da fita de cada vez utilizando um cabeçote de leitura e escrita, executando assim a programação que lhe fosse passada. Outro modelo se baseia em [[recursividade|funções recursivas]] compostas para operar diretamente sobre os números. Uma abordagem similar é o [[Cálculo Lambda|cálculo lambda]]. Outra classe de abordagens trabalha com regras gramaticais operando sobre cadeias de caracteres, como é o caso dos [[cadeias de Markov]] e dos [[sistemas de Post]].
Linha 196 ⟶ 195:
== Ver também ==
* [[Problemas em aberto da Ciência da computação]]
{{Referências}}
== Ligações externas ==
| |||