Buscar

FUNDAMENTOS A CIÊNCIA DA COMPUTAÇÃO E COMPUTABILIDAD

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

�
��
CIÊNCIA DA COMPUTAÇÃO
ANÁLISE DE COMPUTABILIDADE E COMPLEXIDADE DE ALGORITMOS
Professora Regina
 �
FUNDAMENTOS A CIÊNCIA DA COMPUTAÇÃO E COMPUTABILIDADE
Alunos do 4º Semeste:
Dyana Paula Duarte Figueiró. . . . . . . . . . . . . . . . . . . . . . . . . . . 1299112876
Edivino Felipe dos Reis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1299112703
Marco Aurélio Junqueira. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1299112882
Campinas, 14 de Setembro de 2016.
�
SUMÁRIO
1. RESUMO	3
2. ABSTRACT	4
3. INTRODUÇÃO	5
4. PROBLEMAS INDECISÍVEIS OU NÃO COMPUTÁVEIS	6
5. TESE DE CHURCH-TURING	6
6. MÁQUINAS DE TURING
6.1 MÁQUINA DE TURING DE UMA FITA	6
6.2 MÁQUINA DE TURING UNIVERSAL	7
6.3 MÁQUINA DE TURING ALTERNADA	7
6.4 MÁQUINA DE TURING MULTIFITA	7
6.5 MÁQUINAS DE TURING DETERMINÍSTICAS	7
7. CONCLUSÃO	8
8. BIBLIOGRAFIA	9
�
RESUMO
A teoria da recursão, ou teoria da computabilidade foi originado na década de 30, na área de lógica matemática, com os estudos de funções computáveis e dos graus de Turing. 
Os resultados obtidos por pesquisadores, entre eles Alonzo Church e Alan Turing, estabeleceram a computabilidade como uma formalização de uma ideia informal do cálculo efetivo. A partir desses resultados foi formada a tese Church-Turing, que simplificadamente diz que qualquer função que é computável por um algoritmo é uma função computável. 
Após a definição do calculo efetivo, vieram algumas provas que determinados problemas matemáticos não podem ser efetivamente decididos (ou computados), os chamados paradoxos. 
Em relação as máquinas de Turing, eram modelos abstratos de um computador, na qual sua função se restringia aos aspectos lógicos formado por memória, estados e transições.
Sua criação mais famosa foi a máquina Universal, uma máquina de suma importância para o final da segunda guerra mundial. Com ela foi possivel quebrar códigos secretos dos alemães, assim propiciando uma redução de aproximadamente 20 anos de duração da guerra.
Palavras-Chave: Teoria da recursão, Tese Church-Turing, Máquinas de Turing, Máquina universal.
ABSTRACT
The recursion theory, or computability theory has been originated in the 30 decade, in the logic mathematics area, with the study of computable functions and the study of the degrees of Turing. 
The obtained results by researchers, among them, Alonzo Church and Alan Turing, established the computability as a formalization of an informal idea about the effective calculation. From these results, was formed the Church-Turing thesis, which says that any computable function by an algorithm is a computable function. 
After the definition of the effective calculation, came some evidences that certain mathematical problems can’t be effectively decided (or computed), the paradoxes. 
In relation to the Turing’s machines, it was abstract models of a computer, which the function was limited to logical aspects formed by memory, states and transitions.
His most famous creation was the universal machine, an important machine to the end of the World War II. With it was possible to break secret codes of the Germans, providing a reduction of approximately 20 years of war time.
Key words: Recursion Theory, Church-Turing Thesis, Turing’s Machines, Universal Machine.
INTRODUÇÃO
O termo computabilidade, definido por Alan Turing em 1936, nasceu do propósito de solucionar problemas matemáticos através de meios finitos. Um problema é considerado computável quando ele se torna definível, tendo um algoritmo que o descreve e que seja executado por uma máquina de Turing.
A teoria da computação teve seu inicio na década de 30, com o desenvolvimento do cálculo lambda, um sistema formal que estuda funções recursivas computáveis.
Essa teoria se aplica em problemas escritos em maneira formal (algoritmos), dizendo se podem ser solucionáveis por um modelo computacional. 
Em 1936, o matemático inglês Alan Turing propôs um formalismo para a representação de procedimentos efetivos, sendo este o primeiro trabalho a identificar programas escritos para uma máquina computacional autômota. Curiosamente, o cientista americano Alonzo Church, paralelamente publicava um trabalho parecido. 
Com isso foi criada a famosa tese Church-Turing, que simplificadamente diz que qualquer função que é computável por um algoritmo é uma função computável. 
Desde então, foram propostas diversas maneiras de estudo na área da computabilidade, propondo problemas computáveis e buscando sua solução através de algoritmos. 
Na decada de 40, em plena segunda guerra mundial, Alan Turing foi o responsável pela criação da Máquina Universal. Um modelo abstrato de um computador, limitado aos aspectos lógicos do seu funcionamento, que tinha como função decifrar códigos alemães beneficando os aliados na segunda guerra mundial.
	A máquina Universal foi um sucesso, uma aliada imprescindível para a vitória da segunda guerra mundial, reduzindo a duração da guerra em 20 anos e poupando milhares de vidas. Ela é considerada por muitos como o primeiro computador com programa armazenado, e ponto de original para os atuais computadores.
PROBLEMAS INDECISÍVEIS OU NÃO COMPUTÁVEIS
Para um problema ser solucionado, requer um alfabeto (Σ) com uma linguagem (L) de reconhecimento. Resolver tal problema é definir se a palavra em questão é reconhecida pela linguagem. O número de linguagens de um alfabeto não é quantificável, mas, mesmo sendo difícil de provar, existem problemas que não são computáveis.
TESE DE CHURCH-TURING
A tese de Church-Turing ou tese de Church, se baseia no conceito de que, se um problema é definível, ou seja, tem uma sequência de passos finitos para sua resolução e é computável, logo pode ser executado por uma máquina de Turing. Sua tese é baseada na intuição, na noção de algoritmo, não tem como demonstrar, mas é sustentada pelo formalismo de Turing.
“A capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação”
MÁQUINA DE TURING DE UMA FITA
Basicamente, uma máquina de Turing é composta por fita, uma fita infinita dividida em partes chamadas células, onde cada célula pode armazenar apenas uma letra do alfabeto, e quando não é escrito nenhuma letra na célula, ela contém o símbolo □, dito como célula em branco. 
Contém também um conjunto de estados finito, entre eles o estado inicial e estado final. Um cabeçote de leitura ou escrita, que em um determinado momento se encontra sobre uma das células da fita, podendo andar tanto para direita (R), quanto para esquerda(L), a movimentação é definida pela função transição que a máquina executar. O cabeçote pode atuar em uma célula de cada vez, podendo ler e escrever na fita, seguindo a regra da transição.
Uma MT(Máquina de Turing) é definida por M = (Q, Σ, Γ, δ, s0, B, F)
Q = Conjunto de Estados
Σ = Alfabeto de Entrada
Γ = Alfabeto da Fita
δ = Função Transição
S0 = Estado inicial
B = Branco
F = Conjuntos dos Estados Finais
MÁQUINA DE TURING UNIVERSAL
Quando se fala em máquina universal, se fala em uma máquina com capacidade de simular outra máquina, lendo sua descrição e entrada, fazendo exatamente o que a máquina original faz, seguindo sua sequência M.
MÁQUINA DE TURING ALTERNADA
A máquina de Turing alternada com k fitas, é não determinista,ou seja, cada passo é escolhido entre várias possibilidades. A máquina requer que o estado inicial seja de aceitação.
 
A MTA é uma quíntupla, M = (Q, Σ, δ, q0, g)
Q = Conjunto de Estados
Σ = Alfabeto de Entrada
δ = Função Transição
q0 = Estado Inicial
g = Especifica os tipo de estados em estados universais(∀), existenciais(∃), rejeição(rej) e aceitação(ace).
MÁQUINA DETURING MULTIFITA
Uma máquina de Turing multifita é composta por controle, um conjunto finito de estados, entre eles estado inicial, rejeição e aceitação. Cabeças, cada fita têm sua cabeça de leitura, onde ela lê e escreve, e pode ir para a direita ou esquerda. Fitas, onde a primeira armazena a entrada.
A máquina contém várias fitas, e cada uma delas tem sua cabeça de leitura e escrita. De início, a palavra de entrada se encontra na primeira fita, e as outras fitas restantes permanecem em branco. As cabeças de leitura podem se mover para escrever ou ler simultaneamente, de acordo com a função transição. Também é descrita por M = (Q, Σ, Γ, δ, s0, B, F).
MÁQUINAS DE TURING DETERMINÍSTICAS
Se a tabela de ação tem no máximo uma entrada para cada combinação de símbolo e estado então a máquina é uma máquina de Turing determinística (MTD). Se a tabela de ação contém múltiplas entradas para uma combinação de símbolo e estado então a máquina é uma máquina de Turing não-determinística (MTND ou MTN).
OBS. As máquinas de Turing não determinísticas são equivalentes às Maquinas de Turing determinísticas.�
CONCLUSÃO
A partir do estudo realizado para elaboração deste trabalho, é possivel compreender os princípios para compreensão da teoria da computabilidade, as máquinas de Turing e os elementos de computabilidade. Agregando assim, conhecimento sobre o assunto abordado.
	 Vimos que as ideias de computabilidade não estavam formalizadas antes dos resultados de Alan Turing. E devido ao seu trabalho, que foi a origem do computador moderno, pudemos ter a noção necessária para a elaboração de um autômoto.
	Nosso grupo considera este fase da computação como o mais importante de toda a história da computação, pois além de ser o ponto de partida para as tecnologias que temos hoje, foi graças a máquina Universal que pode ser encurtado o período de guerra, assim poupando milhares de vidas.
�
BIBLIOGRAFIA
Wikiversidade. 13 de fevereiro de 2013. Disponível em: <https://pt.wikiversity.org/wiki/Teoria_da_Computa%C3%A7%C3%A3o/Introdu%C3%A7%C3%A3o>. Acesso em: 12 de setembro de 2016.
http://www.dcc.fc.up.pt/~nam/publica/compdec.pdf
http://webpages.fc.ul.pt/~gmferreira/Tese_Mestrado.pdf
Faculdade anhanguera de CAMPINAS – UNIDADE 3
Ciência da Computação (Bacharelado ( 4º Semestre ( ANÁLISE DE COMPUTABILIDADE E COMPLEXID. DE ALGORITMOS.
� PAGE \* MERGEFORMAT �9�

Outros materiais