Máquina de Turing Resumo

Prévia do material em texto

ESTADO DE MATO GROSSO
SECRETARIA DE ESTADO DE CIÊNCIA E TECNOLOGIA
UNIVERSIDADE DO ESTADO DE MATO GROSSO
CAMPUS UNIVERSITÁRIO DE BARRA DO BUGRES
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
Discentes: Everson Dias
Julio Cesar de Camargo
Marcio Silva
Nilton Cesar
Reyllan Raphael
Thiego Ramos Moura
Professor: Me. Luciano barco - Linguagens Formais e Autômatos
MÁQUINA DE TURING
Em 1936, Alan Mathison Turing - um matemático, lógico, criptoanalista e cientista da computação britânico, propôs o que hoje é conhecida como máquina de Turing. Com grande importância para a área informacional computacional, pois possui no mínimo o mesmo poder computacional de qualquer computador de propósito geral. Devido a sua importância, este trabalho tem o objetivo de apresentar a máquina de Turing baseados nos conhecimentos retirados através de pesquisas bibliográficas. 
Os aspectos básicos das máquinas de Turing são semelhantes aos dos autômatos finitos e autômatos de pilha, mas são capazes de reconhecer linguagens que são impossíveis para estes autômatos. Sua composição básica consiste em um controle finito, uma fita e um cabeçote que pode realizar leituras ou escritas na fita. 
Figura 1 - Modelo conceitual da máquina de Turing. Disponível em: <www.ufrgs.br/alanturingbrasil2012/Maquina_de_Turing.pdf>;
Existem outras formas mais sofisticadas das máquinas de Turing que são compostas por múltiplas fitas, máquinas com dispositivos de memória que podem ser lidos ou gravados em regime de acesso aleatório, mas nenhum dos modelos apresenta um poder computacional maior do que a forma básica. Uma visão amplamente aceita é de que qualquer forma aceitável de expressões das ideias contidas em um algoritmo seja em ultima instância, equivalente à que pode se obter empregando-se uma maquina de Turing. Uma máquina de Turing consiste de um controle de estados finito associado a uma unidade de fita. A comunicação entre ambas é proporcionada por um simples cabeçote responsável pela leitura e escrita dos símbolos impressos na fita. A unidade de controle opera de forma que a cada passo ela realiza duas operações, que dependem do seu estado atual e do símbolo lido da fita pelo cabeçote. 
Como ilustrado (figura 1), a fita é delimitada na extremidade esquerda, mas pode estender-se indefinidamente para a direita. Para delimitar a extremidade esquerda utiliza-se o símbolo de um triângulo equilátero que aponta para a direita e sempre que o cabeçote encontrar este símbolo move-se automaticamente uma posição para a direita. Uma máquina de Turing é alimentada gravando-se previamente a cadeia de entrada nas células mais a esquerda da fita, imediatamente a direita do símbolo triangular, sendo o restante da fita preenchido com espaços em branco, representados pelo símbolo de um quadrado sem a haste superior. Os símbolos de setas para a direita e pra esquerda denotam o movimento do cabeçote, para esquerda ou para direita, respectivamente, sendo que nenhum dos dois pode ser membro de qualquer alfabeto utilizado. A máquina é livre para modificar o conteúdo de qualquer posição da fita, seja na sua cadeia de entrada assim como nos infinitos espaços em brancos existentes à direita dela. Definindo formalmente a máquina de Turing seria conceituada como uma quíntupla contendo os elementos: 
A máquina de Turing consiste em um controle finito, que pode se encontrar em qualquer estado de um conjunto finito de estados. Existe uma fita dividida em quadrados ou células em que cada célula pode conter qualquer símbolo de um número finito de símbolos. Uma string finita escolhida a partir do alfabeto de entrada é colocada inicialmente na fita. Todo restante da fita, do infinito à esquerda ao infinito a direita contém o símbolo branco. Existe uma ponta da fita que fica sempre posicionada em uma das células da fita, e inicialmente essa ponta da fita fica na célula mais a esquerda que contém a entrada. 
O movimento da máquina de Turing é uma função do estado de controle finito e do símbolo da fita. Em um movimento a máquina de Turing pode mudar de estado, gravar ou ler um símbolo e para isso movimenta a cabeça da fita para a direita ou para a esquerda. A notação formal para a máquina de Turing (MT) se dá pela tupla de sete valores conforme o exemplo abaixo.
Sendo assim, toda MT tem em principio uma fita infinitamente longa, mas após um número finito de movimentos, apenas um número finito de células pode ser visitada. Assim somente é mostrada uma descrição instantânea, as células que estão entre as brancas mais a esquerda e mais as brancas mais a direita. No caso da cabeça estar varrendo uma das células não brancas de uma das extremidades, um número finito de células brancas à esquerda ou a direita da parte da fita sem células brancas deve ser incluídas na descrição instantânea.
Além da fita devemos também incorporar o controle finito e o cabeçote da fita. Para isto, o estado será colocado imediatamente à esquerda da célula varrida. Entretanto não podemos usar para representar o estado nenhum símbolo que também seja um símbolo de fita. Deste modo deve-se usar uma string como a seguintes características X1, X2 ... Xi - 1q Xi Xi + 1 ... Xn para representar uma Descrição instantânea, em que: 
Q é o estado da MT.
A cabeça da fita está varrendo X símbolo. 
X1, X2 ... Xn é a parte da fita entre o não branco mais a esquerda e o não branco mais a direita. 
 
O movimento da máquina de Turing fica da seguinte forma:
Turing provou que para qualquer sistema formal existe uma máquina de Turing que pode ser programada para imitá‐lo. Era este sistema formal genérico, com a habilidade de imitar qualquer outro sistema formal, o que Turing procurava essencialmente. Tais sistemas chamam‐se Máquinas de Turing Universais. O lógico matemático chegou a definir que: “Qualquer processo aceito por nós homens como um algoritmo é precisamente o que uma máquina de Turing pode fazer” – 1936, mostrou ainda seus resultados para John Von Neumann (cientistas com grandes contribuições para área de ciência da computação) em Princeton, quando os computadores, no sentido moderno, ainda não existiam. Turing criou os conceitos e a fundamentação matemática, que nove anos depois seria a tecnologia utilizada para materializar os primeiros computadores eletrônicos, com grande participação de Neumann, ou seja, a transformação da lógica de suas ideias abstratas em engenharia real. Durante este período de tempo, Turing retornou à Inglaterra e a ideia viveu apenas em sua mente. A correspondência entre instruções lógicas, a ação da mente humana e uma máquina, que poderia ser fisicamente construída, foi a contribuição definitiva de Alan Mathison Turing.
Referências Bibliográficas
Stuart Russell and Peter Norvig, Artificial Intelligence - A Modern Approach. Prentice Hall, 1995. Acesso em: agosto de 2016.
Máquina de Turing. Disponível em: <http://www.ufrgs.br/alanturingbrasil2012/Maquina_de_Turing.pdf>. Acesso em: agosto de 2016.