Aspectos teóricos da computação - Máquina de Turing

UNIP – UNIVERSIDADE PAULISTA

CAIO HENRIQUE NEGRISOLI DE OLIVEIRA

THAIS FERNANDA MADEIRA BENEDETTI

ASPECTOS TEÓRICOS DA COMPUTAÇÃO: MÁQUINA DE TURING

SÃO JOSÉ DO RIO PRETO - SP

2017

SUMÁRIO

1 INTRODUÇÃO        3

1.1 Alan Mathison Turing        3

1.2 Máquina de Turing        3

2 REFERÊNCIAS BIBLIOGRÁFICAS        5

---

---

1 INTRODUÇÃO

Um sistema formal ou um sistema lógico, pode ser definido como qualquer sistema de pensamento abstrato bem definido, em um modelo matemático. A implicação de um sistema por sua base lógica é o que distingue o sistema formal de outros que podem ter alguma base em um modelo abstrato. Muitas vezes, o sistema formal será a base, ou será identificado por si só, como uma teoria maior ou um campo consistente com o uso da matemática moderna.

Cada sistema formal tem uma linguagem formal, que é composta por símbolos primitivos. Esses símbolos agem com uma certa regra de formação, o sistema por tanto, consiste em um número de fórmulas construídas através de finitas combinações dos símbolos primitivos, combinações estas, formadas a partir de axiomas em concordância com as regras estabelecidas.

1. Alan Mathison Turing

Em 1928, Alan Turing começou a estudar a Teoria da Relatividade, conhecendo Christopher Morcom, que foi seu grande influenciador. Após a morte de Morcom, Turing se dedicou ao estudo da teoria mecânica quântica.

Em 1936, Turing consagrou-se como um dos maiores matemáticos do seu tempo, quando constatou que era possível executar operações computacionais sobre a teoria dos números por meio de uma máquina que tivesse embutidas as regras de um sistema formal. Sua descoberta abriu uma nova perspective no esforço de formalizar a matemática, e, ao mesmo tempo, marcou a história da computação.

Alan Turing descreveu em termos matematicamente preciosos como um sistema formal automático, com regras simples de operação. Quando ele uniu matemática e lógica na forma de uma máquina, tornou possíveis sistemas processadores de símbolos.

Quando a Segunda Guerra Mundial eclodiu, Turing foi trabalhar no Departamento de Comunicações da Gran Bretanha, em Bickinghamshire, com o intuito de quebrar o código das comunicações alemãs. Esse código era constantemente trocado, obrigando os inimigos a tentar decodificá-lo antes de ser trocado novamente.

1. Máquina de Turing

A Máquina de Turing também conhecida como Máquina Universal por conseguir trabalhar com qualquer tipo de algoritmo, foi criada pelo matemático britânico Alan Turing (1912 – 1954).

A máquina funcionava através de uma fita dividida em quadrados, que pudesse ler e escrever símbolos.  Uma cabeça de leitura/gravação se moveria em qualquer direção ao longa da fita, um quadrado de cada vez, e uma unidade de controle poderia interpretar uma lista de instruções simples sobre leitura e gravação de símbolos nos quadrados, movendo-se ou não para a direita ou esquerda.  O quadrado lido em cada etapa é conhecido como quadrado ativo.  A regra que está sendo executada é chamada de estado da máquina, e sua fita é potencialmente infinita.

Imagine os símbolos "I" e "-"(branco).  Suponha que o dispositivo possa limpar qualquer um deles quando ele os lê em um quadrado ativo e trocá-lo por outro (apagar "I" e substituir por "-" e vice-versa).  O dispositivo pode mover a cabeça de leitura e de gravação para a direita ou esquerda, de acordo com instruções interpretadas pela unidade de controle.  As instruções podem limpar um símbolo, escrevê-lo ou deixá-lo como está, de acordo com o símbolo lido.

Dado um quadrado que seja uma posição inicial de uma seção da fita preenchida por quaisquer caracteres ou brancos, o dispositivo executa ações especificadas por uma lista de regras, seguindo-as uma por vez até chegar àquela que force sua parada (se não há uma instrução explícita na tabela para uma determinada configuração da fita, então não há nada que a máquina possa fazer quando alcança aquela configuração, encerrando a execução, portanto).  Cada instrução - ou regra - estabelece uma ação a ser executada se houver determinado símbolo no quadrado ativo no tempo em que é lido.