Ciência da Computação na disciplina: Linguagens Formais e Autômatos
Por: CoutinhoNetto • 12/3/2019 • Trabalho acadêmico • 4.121 Palavras (17 Páginas) • 185 Visualizações
[pic 1]
INSTITUTO DE CIÊNCIAS E TECNOLOGIA - ICET
CAMPUS - MANAUS
CIÊNCIA DA COMPUTAÇÃO
MÁQUINA DE TURING
MANAUS-AM
2018
JOSÉ VALENTE COUTINHO NETO - N979BG0
MÁQUINA DE TURING
Trabalho elaborado para obtenção de nota no curso: Ciência da Computação na disciplina: Linguagens Formais e Autômatos com Orientador: Warteloo Silva
MANAUS-AM
2018
Resumo
O presente trabalho tem como objetivo mostrar sobre a Máquina de Turing, na qual é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais. Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições) e não à sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.
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 de computador universal.
Sumário
1. INTRODUÇÃO 6
1.1. Alan Turing 6
1.2. Decifrando o Enigma 7
1.3. Turing e sua Máquina 8
2. Máquina de Turing 9
3. Visão Geral 11
4. Descrição informal 11
5. Modelos equivalentes ao modelo da máquina de Turing 14
6. Limitações da Máquina de Turing 15
6.1. Concorrência 16
7. Máquinas de Turing Universais 17
8. Referências 19
INDICE
Figura 1 Alan Turing, O Pai da Computação fonte: (Alan Turing Aged 16.jpg). 7
Figura 2 Versão reconstruída de uma bombe, no Museu de Bletchley Parck (Fonte da imagem: Wikimedia Commons) 8
Figura 3 Máquina de Turing (Fonte da imagem: The History of Computer Project) 9
Figura 4 Esquema exemplificando o funcionamento da Máquina de Turing 13
Figura 5 Segundo processo da Máquina de Turing 13
- INTRODUÇÃO
- Alan Turing
Alan Mathison Turing OBE (Paddington, Londres, 23 de junho de 1912 - Cheshire East, Cheshire, 7 de junho de 1954) foi um matemático, lógico, criptoanalista e cientista da computação britânico. Foi influente no desenvolvimento da ciência da computação e na formalização do conceito de algoritmo e computação com a máquina de Turing, desempenhando um papel importante na criação do computador moderno. Foi também pioneiro na inteligência artificial e na ciência da computação. É conhecido como o pai da computação.
Durante a Segunda Guerra Mundial, Turing trabalhou para a inteligência britânica em Bletchley Park, num centro especializado em quebra de códigos. Por um tempo ele foi chefe do Hut 8, a seção responsável pela criptoanálise da frota naval alemã. Planejou uma série de técnicas para quebrar os códigos alemães, incluindo o método da bomba eletromecânica, uma máquina eletromecânica que poderia encontrar definições para a máquina Enigma.
Após a guerra, trabalhou no Laboratório Nacional de Física do Reino Unido, onde criou um dos primeiros projetos para um computador com um programa armazenado, o ACE. Posteriormente, Turing se interessou pela química. Escreveu um artigo sobre a base química da morfogênese e previu reações químicas oscilantes como a Reação de Belousov-Zhabotinsky, que foram observadas pela primeira vez na década de 1960.
A homossexualidade de Turing resultou em um processo criminal em 1952, pois atos homossexuais eram ilegais no Reino Unido na época, e ele aceitou o tratamento com hormônios femininos e castração química, como alternativa à prisão. Morreu em 1954, algumas semanas antes de seu aniversário de 42 anos, devido a um aparente auto administrado envenenamento por cianeto, apesar de sua mãe (e alguns outros) terem considerado sua morte acidental. Em 10 de setembro de 2009, após uma campanha de internet, o primeiro-ministro britânico Gordon Brown fez um pedido oficial de desculpas público, em nome do governo britânico, devido à maneira pela qual Turing foi tratado após a guerra. Em 24 de dezembro de 2013, Alan Turing recebeu o perdão real da rainha Elizabeth II, da condenação por homossexualidade.
[pic 2][pic 3]
- Decifrando o Enigma
O primeiro destaque da vida de Turing veio quando ele estava perto dos 30 anos. Trabalhando em conjunto com uma organização inglesa, o matemático foi capaz de criar um sistema para traduzir os textos encriptados pelos alemães chamado “bombe”. Sua máquina era extremamente eficaz contra o equipamento inimigo, que usava uma encriptadora chamada Enigma para fazer com que as mensagens captadas pelos britânicos não fossem compreensíveis.
A bombe captava e identificava quando o sinal estava protegido pelo mesmo padrão da Enigma, para depois usar um padrão de lógica que ignorava informações que se contradiziam e gerar a mensagem verdadeira. Na época, já haviam algumas máquinas que faziam o mesmo, mas nenhuma tão bem quanto esta.
...