Recursos Computacionais
Maquinas de Turing: Uma visão
pragmática
Álvaro Vinícius de Souza Coêlho
[email protected]
Roteiro
• Introdução
• Contextualização
• O problema que o mundo queria resolver
• Maquinas de Turing específicas (MT)
• Maquina de Turing Universal (MTU)
• Arquitetura de Von Newman
• Conclusão
Introdução
• Para entender “esse” Turing:
– MTU: autômatos finitos determinísticos
– Matemática abstrata e não um objeto
– Maquina capaz de resolver todo tipo de
problema matemático
Introdução
• Computar: fazer cálculos, contar, efetuar
operações aritméticas
• Os computadores eletrônicos já estão entre nós
há cerca de 60 anos
• Fundamentos em que se baseiam remontam a
centenas ou até mesmo milhares de anos
Introdução
• Computador: mecanismo ou máquina que auxilia essa
tarefa, com vantagens no tempo gasto e na precisão
• Motivação: livrar-se dos trabalhos manuais,
repetitivos e ergonomicamente contra-indicados
– Cálculos
– Tarefas repetitivas
– Monitoramento
– ...
Ábaco
• Primeiro dispositivo manual de cálculo;
servia para representar números no sistema
decimal e realizar operações com eles
• O mais antigo: 3500 a.C. no Vale entre os
rios Tigre e Eufrates
• Suan-Pan: China
• Soroban: Japão
Ábaco
Uma vareta para cada dígito
John Napier
• Nobre escocês de Edimburgo, o
matemático John Napier, inventou os
logaritmos
• Régua de cálculos (primeiro computador
analógico da história): pequena régua que
deslizava sobre uma base fixa, na qual
haviam diversas escalas para a realização de
determinadas operações
John Napier
Blaise Pascal
• Em 1642, aos 18 anos, inventou a primeira
máquina automática de calcular, feita de rodas
dentadas que simulavam o funcionamento do
ábaco (sistema decimal)
• Ajudar no seu serviço de contabilidade
Blaise Pascal
• Realizava apenas soma e subtração e o
resultado era mostrado numa seqüência de
janelinhas.
• Pascalina ou Máquina Aritmética de Pascal:
primeira calculadora mecânica
Blaise Pascal
Gottfried Wilhelm von Leibnitz
• Introduziu o conceito de realizar
multiplicações e divisões através de adições e
subtrações sucessivas
• Aos 12 anos já estudava Latim e Grego como
autodidata. Antes de ter 20 anos já possuía
mestrado em matemática, filosofia, teologia e
leis
Gottfried Wilhelm von Leibnitz
• Em 1672, aperfeiçoou a Máquina de Pascal,
construindo a calculadora universal
Joseph Marie Jackuard
• Em 1801 construiu um tear automático que
aceitava entrada de dados através de cartões
perfurados para controlar a confecção e
desenho dos tecidos
• Esta máquina pode ser considerada a
primeira máquina mecânica programável
Joseph Marie Jackuard
Charles Babbage
• Em 1822, idealizou a Máquina das Diferenças,
que consistia num dispositivo mecânico
baseado em rodas dentadas, para a avaliação de
funções e a obtenção de tabelas
• Mas esta máquina não chegou a ser construída
devido as limitações tecnológicas da época
(limites do ferramental industrial)
Charles
Babbage

Ao operador cabia
somente iniciar a
cadeia de
operações, e a
seguir a máquina
tomava seu curso
de cálculos,
preparando
totalmente a
tabela prevista
Charles Babbage
• Em 1833, projetou a Máquina Analítica ou
Diferencial, dispunha de programa, memória,
unidade de controle e aritmética e periféricos
de entrada e saída
• Realizava automaticamente tabelas de
logaritmos e funções trigonométricas
• Babbage o “ Pai da Informática ”
Charles
Babbage
O Problema que o Mundo Queria
Resolver
• Máquinas que resolviam problemas
específicos
• Décimo problema de Hilbert –
Entscheidungsproblem (1900 – 1928):
– Será possível se definir um procedimento
mecânico para resolver os problemas da
matemática um após o outro?
Turing
• Alan Mathison Turing nasceu em 23 de junho
de 1912 em Londres
• Na infância distraia-se fatorando números
• A maior parte do seu trabalho foi desenvolvido
no serviço de espionagem, durante a II Grande
Guerra
• Matemático extraordinário decifrador de
códigos e cientista da computação
Turing
• 1975 foi reconhecido como um dos grandes
pioneiros no campo da computação
• Em 1936 Alan M. Turing desenvolveu a
construção teórica das “Máquinas de Turing”
(1935 –36)
– Matemática abstrata e não um objeto
– Maquina capaz de resolver todo tipo de problema
matemático (?)
Turing
• Questão1 : existe um procedimento mecânico
geral para resolver todos os problemas
matemáticos? Um após outro?
• Questão 2: existe limitação àquilo que um
algoritmo pode fazer a princípio?
Turing
• Teoria Matemática da Computação define um
algoritmo como a representação formal e
sistemática de um processo, e através da qual
se demonstra que nem todos os processos são
representáveis
Turing
• De qualquer ângulo que se examine a
idealização de Turing sempre se verá uma
semelhança muito grande com os
computadores atuais
• 1º Passo: mostrou que poderia ser construída
uma MT para cada problema com solução
algorítmica
– De somar 1 a um número a decifrar código
Turing
• Arquitetura: Uma fita infinita, uma cabeça de
leitura-gravação, uma máquina de estados que
pode se mover na fita à direita ou à esquerda
Turing
• Arquitetura: seqüência linear de marcas na fita (0´s e
1´s) representando números finitos lidas uma por vez
• Não se trata de codificação binária!
• A descrição do algoritmo deve ser finita e executável
em tempo finito
• Função de Transição: diz “o que vazer”, ou seja,
comanda as leituras e gravações, o sentido de
movimento da cabeça e define o estado da máquina
Turing
• Idéia de Turing: a partir do símbolo lido na
fita e da função de transição atual a máquina
decide o que fazer (determinística)
• Operações rotuladas: substituições explícitas
– Ex: 101 ->131E
Turing
• MT: definição matemática de uma operação
mecânica
• Familiarizando-nos com MT simples o
entendimento das complexas será mais fácil
• MT N+1:
–
–
–
–
00  00D
01  11D
10  01PARE
11  11D
Turing
• Exemplo: Na fita: ...00001110000... (o
número 3)
• Saída esperada: ...00001111000 ... (o número
4)
... Acompanhando o trabalho da MT ...
Turing
• 2º Passo: Uma máquina de Turing Universal
– Crítica: Construir uma MT para cada problema?
Impraticável!
– MTU!
– Problema: Onde armazenar as informações de que
MTU precisa para simular qualquer MT?
– Alternativa: E se houvesse uma MT que lesse na
fita a entrada do problema E as instruções?
Turing
• Modelo matemático dos computadores de
hoje:
– Propósito geral
• Como armazenar as instruções na fita?
– Os dados são armazenados com codificação
binária estendida (poderia ser binário simples)
Turing
• Mostraremos os princípios, detalhes são
muito complicados
• Idéia básica: codificar a lista de instruções de
MT arbitrária num grupo de 0´s e 1´s para
serem representados na fita
• Parte inicial da fita tem as instruções que
atuarão sobre os dados que vêm em seguida
Turing
• Chegamos no famoso: Número de Turing!!!!!
– Código binário final transformado em decimal!!!!
– Todo programa de computador (tira de bits) pode
ser mapeado em um e somente um número
natural e vice-versa!!!!!!
– Geração automática de programas... Perderemos
nossos empregos!!!!!!!!
– Vejamos:
• MTn: Máquina de Turing que executa o algorítmo N
Esquema Geral 1: Beco sem
saída
main() {
int satisfaz(int N,M) {
int N=1
int R
while(!(satisfaz(N,M))) cria_programa(N)
N++
cria_dados(M)
}
R = system(N(M))
if (R = previsto)
return TRUE
Se a chamada
else
N(M) entra em
return FALSE
“laço infinito”, R
}
jamais recebe um
valor!
Esquema Geral 2: Beco sem
saída?
main() {
int satisfaz(int N,M) {
int N=1
int R
while(!(satisfaz(N,M)))
cria_programa(N)
N++
cria_dados(M)
}
if pára(N,M) {
R = system(N(M))
if (R = previsto)
return TRUE
Este teste, se
else
exeqüível, impede
return FALSE
que nosso gerador
}
de programas
else
“trave”!
return FALSE
}
Turing
• Supor que há Pára(N,M) retorna 1 se N(M)
pára e 0 caso contrário
• Multiplicar Pára(N,M) por N(M) dá N(M)
(1*resultado de N(M)) ou 0 (0*qualquer coisa)
• Imaginar Pára(N,N)*(N(N)) é possível? Sem
problemas. Dá N(N) ou 0
• Criar K(N) = Pára(N,N)*N(N) + 1
Turing
• K(K) pára?
– então K(k) = 1*K(K) + 1 = K(K) + 1. Absurdo.
– senão K(K) = 0*K(K) + 1 = 1. Absurdo (K(K) não
tem valor!)
• Portanto não pode haver K(K). Não pode haver
K(N). Não pode haver Pàra(N,N). Não pode
haver Pàra(N,M).
• É impossível fazer o programa gerador de
programas!
Turing
• O décimo problema de Hilbert não tem
solução!
“Será possível se definir um procedimento
mecânico para resolver os problemas da
matemática um após o outro?”
• Não se pode garantir!
Turing
• Todos os computadores modernos de uso geral são
efetivamente máquinas de Turing universais!
• Problema da parada: saber se uma MTn pára ou não
ao atuar sobre o número m
• Impossível decidir...
• Algoritmos que não param não são muito úteis...
Turing
• Ficou também demonstrado a existência de
problemas sem solução algorítmica e chegouse a seguinte conclusão:
Um problema terá solução algorítmica se
existir uma Máquina de Turing para
representá-lo
• Desses estudos surgiu a Teoria da
Computabilidade: Problemas Turing
Computáveis e Não Turing Computáveis (MT
e ~MT)
Turing
• Decidir se MT´s param: importante questão
matemática:
– Teorema de Fermat: análise de todos os quádruplos
naturais (x,y,z,w) possíveis
(x+1)w+3 + (y+1)w+3 = (z+1)w+3
– Conjectura de Goldbach: todo número maior que 2
é a soma de números primos
• Desdobrá-lo em números primos (saber se é primo)
Turing
• A equação x2 – 2x = 0 possui quantas raízes?
– 2 e 4 são raízes óbvias!
– Há uma terceira?
• Não computabilidade da geração dos números
reais
– Corte Diagonal de Cantor
• Programa gerador de programas...
John von Newmann
• Em 1944 desenvolveu a idéia de programa
interno e fundamento teórico de um
computador eletrônico denominado Modelo de
Von Newmann
• Idéia: existência simultânea de dados e
instruções e a possibilidade do computador ser
programado
• Publicou o artigo "Teoria e Técnicas dos
Computadores Eletrônicos", uma tentativa de
projeto de um computador do ponto de vista
lógico
Processador
e memória
de 8 bits
John von Newmann
• Em 1952 esse computador foi construído,
recebeu o nome de EDVAC (Eletronic Discrete
Variable Automatic Computer) e era uma
modificação do ENIAC
• Utilizava tecnologia estranha
– “linhas de retardo acústico de mercúrio por onde
circulavam sinais elétricos sujeitos a retardo”
John von Newmann
• Em 1951 Mauchly constrói o primeiro
computador da série a ser posto à venda, o
UNIVAC-I (computador automático
universal), que já utilizava válvulas e fitas
magnéticas
• No ano seguinte foram construídos os
computadores MANIAC-I, MANIAC-II,
UNICAC-II
• PDP-8 – levou os computadores para
laboratórios e linhas de produção, em 1965
Com o surgimento destas
máquinas acaba a pré-história da
informática ...
... a partir daqui entramos na fase
da EVOLUÇÃO ELETRÔNICA
Conclusão
• As idéias de computabilidade não estavam
formalizadas antes dos resultados de Alan
Turing
• Von Newmann conseguiu tornar factível as
idéias de Turing e Babbage
• As idéias de Babbage, Turing e Newmann
são empregados nos computadores até hoje
• Supercomputadores usam estas mesmas
idéias
Conclusão
• Limite: futuro incerto da computação
quântica, desenvolvimento de máquinas não
determinísticas.
Turing.
FIM!
Escher
“A soma da inteligência no planeta é uma constante;
a população está crescendo”
Lei de Murphy aplicada ao Pensamento