ACA-4.docx

Prévia do material em texto

Relatório técnico
	CIÊNCIA DA COMPUTAÇÃO 
	
Állan Lima da Cunha 9930011572 
Danillo Pery Martins Garcia 2485697013
 
Relatório técnico referente à aplicação dos principais conceitos para a compreensão da noção de computabilidade e dos tipos de máquinas de Turing e suas funções apresentado para avaliação da disciplina “Análise de Computabilidade e Complexidade de Algoritmos”, do curso de Ciência da Computação, da Faculdade Anhanguera educacional unidade III em Campinas-SP. 
O norte americano Alonzo Church (14/06/1903 – 08/11/1995) foi matemático e, atuou principalmente nas áreas de lógica matemática, recursão e teoria da computação. Criou um sistema formal de investigação e aplicação de funções, chamado Cálculo Lambida.
Já Alan M. Turing (23/06/1912 – 07/06/1954), nascido em Londres, matemático, criptoanalista e cientista da computação, foi influente no desenvolvimento da formalização do conceito de algoritmo e da ciência da computação. Dedicou-se a estudar teoremas que podiam ser comprovados e à teoria da computabilidade.
A teoria da computabilidade é constituída pelos estudos da computabilidade e definibilidade em meio ao campo da lógica matemática, podendo também ser chamada de teoria da recursão. Em base, define que todos os mecanismos de computação definem a mesma classe de funções computáveis, isto é, uma determinada máquina pode transpassar seu método de processamento para qualquer outra máquina, apenas por meio da maneira em que ocorre sua codificação.
A tese elaborada por Church e Turing, define que cálculos poderiam ser computados por máquinas sobre determinada orientação em forma de algoritmos. Esses algoritmos seriam sequências finitas de instruções especificas, inequívocas e axiomáticas. A nomenclatura “algoritmo” não especifica que determinada instrução seja aplicada unicamente ao campo da eletrônica digital, mas como também a outros tipos de maquinas que se operem de maneira automatizada, além de que, estende-se também a maneira que determinada pessoa segue uma sequencia de passos para realizar alguma ação.
Turing afirmou que qualquer função considerada calculável poderia ser realizada por uma Máquina de Turing. De forma simplificada, qualquer expressão em que se possa chegar a um resultado final, em que se tenham dados precisos ou consideráveis, possibilita atingir determinado resultado seguindo uma instrução, com suas regras e predefinições. Desta forma, é possível concluir que qualquer Máquina de Turing pode ser transpassada para uma dada linguagem de programação.
Máquina de Turing, Máquina Mundial ou Máquina Universal é um dispositivo teórico ou um molde dos aspectos lógicos do funcionamento de um computador, envolvendo memória, estados e transições.
A Máquina de Turing consiste em uma fita dividida em células adjacentes que contém símbolos de algum alfabeto finito, um símbolo especial branco e, um ou mais símbolos especiais. Esta fita corre para esquerda e para a direita conforme a necessidade da máquina. Possui também um cabeçote que escreve e lê os símbolos na fita e, pode também mover-se para esquerda e para a direita. Possui ainda um registrador de estados que, como o nome já diz, registra os diferentes estados da máquina, desde que atendam aos requisitos da teoria de Church-Turing. A máquina conta também com uma tabela de ações ou função de transição que é responsável por dizer a máquina como mover seu cabeçote, que símbolo escrever e, qual será o seu novo estado.
Além disto, a máquina pode também ser determinística, onde se tem uma única entrada como parâmetro máximo para toda combinação de variável e estado. Caso a entrada possua mais de um parâmetro para combinação de variável e estado, a máquina é não determinística.
Referências
https://pt.wikipedia.org/wiki/Recursividade
https://pt.wikipedia.org/wiki/Redu%C3%A7%C3%A3o_(teoria_da_recurs%C3%A3o)
https://pt.wikipedia.org/wiki/Hist%C3%B3ria_da_tese_de_Church-Turing
https://pt.wikipedia.org/wiki/Teoria_da_computabilidade
https://pt.wikipedia.org/wiki/Tese_de_Church-Turing
http://wiki.icmc.usp.br/images/7/73/SCC0505Cap4.pdf
https://pt.wikipedia.org/wiki/Algoritmo
https://pt.wikipedia.org/wiki/Máquina_de_Turing