A Maquina de Turing

IGOR MORAES DE OLIVEIRA

TÚLIO LEITE DEL RIO

WÁLISSON FERNANDES ALVES

MÁQUINA DE TURING

FRANCA/SP

ABRIL/2023

O início da teoria da computação de turing se deu após o conhecimento do “Problema da decisão” (Entscheidungsproblem), que era um problema proposto por David Hilbert. Esse que consiste em perguntar se existe um método mecânico para determinar se uma dada sentença lógica segue ou não de um conjunto de axiomas.

A percepção genial de Turing foi a substituição da noção intuitiva de procedimento efetivo por uma ideia formal, matemática. O resultado foi a construção de uma conceituação matemática da noção de algoritmo, uma noção que ele modelou baseando-se nos passos que um ser humano dá quando executa um determinado cálculo ou cômputo. Assim ele formalizou definitivamente o conceito de algoritmo.

A máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi projetado pelo matemático britânico Alan Turing (1912-1954), muitos anos antes dos computadores digitais modernos existirem, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos de seu funcionamento (memória, estados e transições) e não à sua implementação física. Uma máquina de Turing pode modelar qualquer computador digital.

Turing definiu que os cálculos mentais consistem em operações para transformar números em uma série de estados intermediários que progridem de um para outro de acordo com um conjunto fixo de regras, até que uma resposta seja encontrada.

Ou seja, uma invenção automática capaz de manipular símbolos em uma fita de acordo com uma série de regras para armazenar informações, assim como os computadores fazem hoje. Assim Turing desenvolveu conceitos de algoritmo - uma receita que mostra passo a passo os procedimentos necessários para resolver uma tarefa.

Esse é um dispositivo físico que manipula automaticamente os símbolos de um sistema formal de acordo com as suas regras, onde esses símbolos são representados na forma de números binários. A máquina teórica de Turing estabelece tanto um exemplo da sua teoria da computação quanto uma prova de que certos tipos de máquinas computacionais poderiam ser construídas. Efetivamente, uma Máquina de Turing Universal, exceto pela velocidade, que depende do hardware, pode emular qualquer computador atual, desde os supercomputadores até os computadores pessoais, com suas complexas estruturas e poderosas capacidades computacionais, desde que não importasse o tempo gasto. Ele provou que para qualquer sistema formal existe uma Máquina de Turing que pode ser programada para imitá-lo. Ou em outras palavras: para qualquer procedimento computacional bem definido, uma máquina de Turing Universal é capaz de simular um processo mecânico que execute tais procedimentos.

A máquina de turing consiste basicamente de três partes: Uma fita, uma unidade de controle e uma função de transição.

Fita: essa é usada como um dispositivo de entrada, saída e memória. Ela é dividida em células que armazenam um símbolo de cada vez. Assume-se que a fita é extensível à esquerda e à direita, ou seja, a máquina de Turing tem tanta fita quanto é necessária para a computação, com uma cabeça que pode ler e escrever símbolos.

Unidade de controle: Reflete o estado de controle da máquina. Possui uma unidade de leitura e gravação que pode deslocar-se para a esquerda ou para a direita da fita, podendo ler e/ou gravar um único símbolo em cada movimento.