trabalho computabilidade

Prévia do material em texto

�
 
CIÊNCIA DA COMPUTAÇÃO
Computabilidade e analise de algoritmos.
Professora Regina
 �
COMPREENDENDO A COMPUTABILIDADE, MÁQUINAS DE TURING E TESE CHURCH-TURING
Felipe Henrique de Paula. . . . . . . . . . . . . . . . . . . . . . . . . .1563286051
Campinas, 16 de Setembro de 2016.
INTRODUÇÃO PARA A COMPREENSÃO DA NOÇÃO DE COMPUTABILIDADE
Sendo um tópico chave dentro da lógica Matemática e da ciência da computação, também para a teoria da computação, juntamente com a teoria da computabilidade, a computabilidade resolve problemas de forma habilidosa e efetiva. Sendo os modelos mais estudados, tais como as funções Turing-Computáveis, funções μ-recursivas, e calculo lambda, ambos tendo poderes computacionais equivalentes. Além dessas funções, outras formas de computabilidade estudadas. Quando se trata de noções de computabilidade mais fracas que as máquinas de Turing, então são estudadas na teoria dos autômatos, enquanto as noções mais fortes, passam a ser estudadas no campo da hipercomputação.
A principal ideia da computabilidade é a dos problemas computacionais, uma tarefa que pode ser explorada.
No objetivo do estudo da solubilidade de problemas, dentro da computabilidade, há uma investigação referente à existência (ou não) de algoritmos, no qual acaba solucionando uma determinada classe de problema, além de investigar limites da computabilidade, e consequentemente do que pode ser implementado em um computador. Além disso, concentra-se nos problemas em respostas binárias, do tipo “sim” ou “não” (problemas sim/não ou problemas de decisão). Há dois tipos de problemas:Os problemas de decisão ou de função. Muitos problemas acabam sendo não solucionáveis, porém algum deles são parcialmente solucionáveis (computáveis) no caso de um algoritmo capaz de responde “sim”, embora, eventualmente, possa ficar em um loop infinito para uma resposta que deveria ser “não”.
MÁQUINAS DE TURING
 ELEMENTOS DA COMPUTABILIDADE, MT DETERMINÍSTICA E TIPOS DE MT E SUAS FUNÇÕES.
Um mecanismo constituído por uma fita dividida em quadrados (a máquina observa apenas um quadrado por vez que pode estar vazia ou conter algum símbolo), que pode ser infinitamente prolongada (tanto para direita, quanto para a esquerda), a máquina de Turing, formou a estrutura para fundamentar a ciência da computação moderna e a computabilidade, onde qualquer processo aceito por nós homens como algoritmo é precisamente o que uma máquina de Turing pode fazer. 
A MT pode decidir quaisquer linguagens livres de contexto, em complemento às linguagens não decidíveis pelo autômato com pilha, como uma linguagem formada por números primos, Por isso, é um modelo de computação estritamente mais poderoso. 
Publicada pela primeira vez em 1936, num artigo intitulado “OncomputableNumbers, withna ApplicationontheEntscheidungsproblem”, em resposta ao tratamento do problema da decisão.
Trata-se de um dispositivo imaginário embasando por uma teoria revolucionária, foi responsável pelo reconhecimento da comunidade científica, declarando Turing com o título simbólico de “pai da computação”.
O leitor da MT, por sua vez, além de realizar a leitura de um único símbolo de um quadrado da fita, pode também apagar os símbolos do quadrado lido e escrever neste mesmo quadrado um símbolo qualquer do alfabeto (nada impede que seja o mesmo), além disso, é possível mover-se um quadrado tanto para esquerda, quanto para a direita.
Em qualquer instante de tempo a Máquina de Turing se encontra em um estado oriundo de um conjunto finito de estados, chamados de estados internos. 
A ação a ser tomada pela mesma, depende de seu estado atual e do símbolo que esta sendo lido no momento. Sendo assim, suas ações podem ser especificadas por um conjunto finito de quádruplas.
A Máquina de Turing pode ser definida como uma máquina que contém um conjunto finito de estados Q com um estado inicial distinto, também, um conjunto finito de símbolos  Σ.
A interpretação e execução dos algoritmos são realizadas por estados e uma função de transição determina o novo conteúdo da fita. Desde modo, por restrição imposta ao algoritmo, pode‐se alterar o conteúdo de apenas um quadrado por vez ou movimentar a cabeça, no máximo uma célula em qualquer direção. É permitida também a utilização de qualquer conjunto finito de símbolos para o alfabeto  Σ, mesmo que a definição original tenha insistido em  Σ  = {0,1}. Esta mudança não tem impacto sobre a definição do conjunto de funções computáveis pela máquina.
Turing também se envolveu na construção de máquinas físicas para quebrar os códigos secretos das comunicações alemãs durante a Segunda Guerra Mundial, tendo utilizado alguns dos conceitos teóricos desenvolvidos para o seu modelo decomputador universal. 
Provou que para qualquer sistema formal existe uma máquina de Turing que pode ser programada para imitá‐lo.
A TESE DE CHURCH-TURING
É um teste sobre a natureza de objetos mecânicos de cálculo, computadores e como eles entendem e executam os algoritmos. 
O principio básico é de que um algoritmo deve satisfazer as seguintes condições:
O algoritmo é um conjunto finito de instruções diretas, e que são descritas com uma quantidade finita de símbolos. O algoritmo sempre vai ter um resultado nesse conjunto de números finitos, passos, instruções. O algoritmo pode ser executado e testado diretamente na folha para depois ser aplicado na máquina e já ter uma noção do resultado esperado e se o algoritmo está se comportando dentro desse conjunto finito de resultados.
A fase de execução não necessita de assistência humana além do necessário para entender o principio básico e executar as instruções.
Bibliografia: 
http://usuarios.upf.br/~mcpinto/teoria/teoria-computabilidade.pdf
http://www.lbd.dcc.ufmg.br/colecoes/wei/2013/0034.pdf
http://wiki.icmc.usp.br/images/7/73/SCC0505Cap4.pdf
http://numeroimaginario.com.br/2015/12/27/teoria-da-recursao-maquinas-de-turing-e-computabilidade-de-funcoes/
http://www.ufrgs.br/alanturingbrasil2012/Maquina_de_Turing.pdf
http://rmu.sbm.org.br/Conteudo/n06/n06_Artigo01.pdf
https://www.lume.ufrgs.br/bitstream/handle/10183/3419/000400280.pdf?sequence=1
Faculdade anhanguera de CAMPINAS – UNIDADE 3
Ciência da Computação (Bacharelado ( 1º Semestre ( Sistemas e Aplicações Multimidia.
� PAGE \* MERGEFORMAT �3�