Teoria da computação

UNIPÊ – Centro Universitário de João Pessoa
Curso de Ciências da Computação

Teoria da Computação
MÁQUINAS UNIVERSAIS
Fabrício Dias [e-mail] Agenda







Algoritmo – Definições
Máquina – Definições
Máquina Universal
Codificação de conjuntos estruturados e programas monolíticos
Exemplos

Algoritmo


Termo usado intuitivamente para a solução de um problema
Problema

ALGORITMO

Solução

Algoritmo
 Solução

de um problema:

Descrição finita e não-ambígua;
 Passos discretos;
 Executáveis mecanicamente em um tempo finito.


4

Algoritmo
 Limitações

de tempo podem, eventualmente, determinar se um algoritmo pode ou não ser utilizado na prática;  Entretanto,

limitações de tempo não são restrições teóricas pois a inexistência de limitações não implica recursos ou descrições infinitas.
5

Algoritmo

Assim, recursos de tempo e de espaço devem ser “tanto quanto necessários”.

6

Algoritmo


Considerando que um algoritmo deve possuir uma descrição finita, alguns tipos de dados podem não satisfazer tal condição, por exemplo os números irracionais 



O número 

Assim, no que segue, o estudo é restrito aos algoritmos definidos sobre o conjunto dos números naturais.
7

Algoritmo
 Algoritmos

definidos sobre o conjunto dos números naturais.


Qualquer conjunto contável pode ser equivalente ao dos naturais, através de uma codificação.

8

Máquina


Conceito:




Interpreta os programas de acordo com os dados fornecidos; É capaz de interpretar um programa desde que possua uma interpretação para cada operação ou teste que constitui o programa.

Máquina
O

conceito de programa satisfaz à noção intuitiva de algoritmo;
 Entretanto, é necessário definir a máquina a ser considerada;
 Tal máquina deve ser suficientemente:
Simples
 Poderosa


10

Máquina


Simples:






Permite estudos de