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
[email protected]
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 propriedades, sem a
necessidade de considerar características nãorelevantes;
Permite estabelecer conclusões gerais sobre a
classe de funções computáveis;
Poderosa:

Capaz de simular qualquer característica de
máquinas reais ou teóricas.
11
Máquina Universal

Se for possível representar qualquer
algoritmo como um programa em
uma máquina, então esta é
denominada de máquina universal.
12
Máquina Universal

Evidências de que uma máquina é
universal:


Evidência Interna. Qualquer extensão das
capacidades da máquina universal não
aumenta o seu poder computacional;
Evidência Externa. Outros modelos que
definem a noção de algoritmo são, no
máximo, computacionalmente equivalentes.
13
Codificação de conjuntos estruturados

Problema da codificação de conjuntos
estruturados:

onde elementos de tipos de dados
estruturados são representados como
números naturais.
14
Codificação de conjuntos estruturados

Definição: para um dado conjunto
estruturado X, a idéia básica é definir
uma função injetora:
c: X → 
ou seja, uma função tal que, para todo
x,y  X, tem-se que:
se c(x) = c(y), então x=y
Neste caso, o número natural c(x) é a
codificação do elemento estruturado x.
15
Exemplo 1

Codificação de n-Uplas Naturais

Suponha que é desejado codificar, de
forma única, elementos de Nn como
números naturais, ou seja, deseja-se uma
função injetora:
c: Nn → N
16
Exemplo 1
Uma codificação simples é a seguinte:
a) pelo Teorema Fundamental da Aritmética,
cada número natural é unicamente
decomposto em seus fatores primos;
17
Exemplo 1
Uma codificação simples é a seguinte:
b) suponha que p1 = 2, p2 = 3, p3 = 5 e
assim sucessivamente. Então, a
codificação
c: Nn → N
definida como segue é unívoca (suponha
(x1, x2, ..., xn) em Nn):
c(x1, x2, ..., xn) = p1x1 * p2 x2 * ... * pnxn
18
Exemplo 2

Codificação de Programas Monolíticos


Um programa monolítico pode ser
codificado como um número natural.
Suponha um programa monolítico
P = (I, r) com n instruções rotuladas onde
{F1, F2, ..., Ff} e {T1, T2, ..., Tt} são os
correspondentes conjuntos de
identificadores de operações e testes;
19
Exemplo 2

Codificação de Programas Monolíticos


a)
b)
Seja P' = (I, 1) como P, onde 1 é o rótulo inicial,
e 0 o único rótulo final;
Assim, uma instrução rotulada pode ser de uma
das duas seguintes formas:
Operação:
r1: faça Fk vá_para r2
Teste:
r1: se Tk então vá_para r2 senão
vá_para r3
20
Exemplo 2

Codificação de Programas Monolíticos
Cada instrução rotulada pode ser denotada por
uma quádrupla ordenada, onde a primeira
componente identifica o tipo da instrução:
a) Operação (0):
r1: faça Fk vá_para r2
(0, k, r2, r2)

Teste (1):
r1: se Tk então vá_para r2 senão
vá_para r3
(1, k, r2, r3)
b)
21
Exemplo 2

Codificação de Programas Monolíticos

Usando a codificação, o programa
monolítico P’, visto como quádruplas
ordenadas pode ser codificado como segue:
 cada quádrupla (instrução rotulada) é
codificada como um número natural.
Assim, o programa monolítico P’ com m
instruções rotuladas pode ser visto como
uma n-upla;
22
Exemplo 2

Codificação de Programas Monolíticos

por sua vez, a n-upla correspondente ao
programa monolítico P’ é codificada como
um número natural, usando a codificação.
23
Exemplo 2

Codificação de Programas Monolíticos


Suponha o número p = (2150)*(3105)
Portanto, o programa possui duas instruções
rotuladas correspondentes aos números 150
e 105. Relativamente às decomposições em
seus fatores primos, tem-se que:
 150 = 21*31*52*70
 105 = 20*31*51*71
24
Exemplo 2

Codificação de Programas Monolíticos

o que corresponde às quádrulas:
(1, 1, 2, 0) e (0, 1, 1, 1), que é o mesmo que:
1: se T1 então vá_para 2 senão vá_para
0
2: faça F1 vá_para 1
25
Exemplo

Codificar o programa monolítico em um
único número natural P1. F->1, G->2.
1:
2:
3:
4:
5:
6:
7:
8:
faça
se T
faça
se T
faça
se T
faça
se T
F vá_para 2
então vá_para
G vá_para 4
então vá_para
F vá_para 6
então vá_para
G vá_para 8
então vá_para
3 senão vá_para 5
1 senão vá_para 0
7 senão vá_para 2
6 senão vá_para 0
26
Exemplo
1:
2:
3:
4:
5:
6:
7:
8:
faça
se T
faça
se T
faça
se T
faça
se T
F vá_para 2 (0, 1,2, 2)
então vá_para 3 senão
G vá_para 4 (0, 2, 4, 4)
então vá_para 1 senão
F vá_para 6 (0, 1, 6, 6)
então vá_para 7 senão
G vá_para 8 (0, 2, 8, 8)
então vá_para 6 senão
vá_para 5 (1, 1, 3, 5)
vá_para 0 (1, 1, 1, 0)
vá_para 2 (1, 1, 7, 2)
vá_para 0 (1, 1, 6, 0)
27
Exemplo
que correspondem aos seguintes números naturais:
1: 20.31.52.72 = 3675
2: 21.31.53.75 = 12605250
3: 20.32.54.74 = 13505625
4: 21.31.51.70 = 30
5: 20.31.56.76 = 5514796875
6: 21.31.57.72 = 7350
7: 20.32.58.78 = 20266878520000
8: 21.31.56.70 = 93750

28
Exemplo

Transformando o programa monolítico
em um número natural, temos que P1:
P1 = 23675 * 312605250 * 513505625
* 730 * 115514796875* 137350
* 1720266878520000 * 1993750
29
Dúvidas????