Teoria da Computação

Teoria da Computação
1.Introdução
Teoria da computação: ciência que procura organizar o conhecimento formal relativo aos processos de computação.
Filósofos sustentam que os computadores não podem computar, porque não compreendem a noção de números, podemos afirmar que os computadores realizam uma “Computação perceptível”, já que transformam uma entrada em saída como se tivessem realmente computando.
2.Algoritmos e Decidibilidade
Algoritmo: descrição finita de um processo de computação, é um texto finito, escrito em uma linguagem algorítmica no qual cada sentença tem um significado não-ambíguo. Deve ser resolvido em tempo finito, deve ter parada garantida.
Procedimento:Não termina necessariamente. Existe problemas que possuem procedimentos para serem resolvidos, mas não possuem algoritmos. Existe procedimentos que podem chegar a uma resposta em tempo finito ou então nunca chegar, ao contrário do algoritmo, que sempre chega em uma resposta falsa ou afirmativa em um tempo finito.
Problema decidível: possui algoritmo que obtenha solução conclusiva para qualquer entrada. Se existe um algoritmo quesempre responda sim ou não pra qualquer entrada, então o problema é decidivel.
Problema indecidíveis ou parcialmente decidiveis: para alguns problemas observou que não existem nem existirão algoritmos assim, são os indecidiveis, ou parcialmente se pelo menos encontrar uma das respostas.
Ex: Uma linguagem L é decidivel, se dada uma sentença W for possível decidir algoritmicamente se W é uma sentença de L.
3.Introdução a especificação e processamento de linguagens de programação
3.1 Especificações de linguagens de programação (LP)
Ao se criar uma LP se define como os programas validos devem se comportar e como se escreve um programa nessa linguagem. Tais especificações envolvem a descrição de um léxico, de uma sintaxe e de uma semântica para a LP.
O léxico da LP: é o vocabulário que pode ser utilizado para formar sentenças na linguagem. Define os itens léxicos da linguagem