Informatica - ICC

Introdução à Ciência da
Computação
Aula 01
Carlos André Guerra Fonseca

Introdução à Ciência da Computação – aula 01
• Modelo de Turing;
• Máquina de Turing;
• Modelo de Von Neumann.

Modelo de Turing
• Primeira ideia de um dispositivo de computação universal, proposto em 1936;
• Modelo abstrato de um computador:
– 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;
• Pode realizar qualquer cálculo se o programa apropriado for fornecido.

Máquina de Turing
• Consiste em:
– Uma fita:
• Dividida em células, uma adjacente à outra;
• Cada célula contém um símbolo de algum alfabeto finito; • O alfabeto contém um símbolo especial branco e um ou mais símbolos adicionais;
• Possui tanta fita quanto é necessário para a computação; • Células que ainda não foram escritas estão preenchidas com o símbolo branco.

Máquina de Turing
• Consiste em:
– Um cabeçote, que pode ler e escrever símbolos na fita e mover-se para a esquerda e para a direita.
– Um registrador de estados, que armazena o estado da máquina de Turing:
• O número de estados diferentes é sempre finito;
• Há um estado especial denominado estado inicial com o qual o registrador de estado é inicializado.

Máquina de Turing
• Consiste em:
– Uma tabela de ação que diz à máquina:
• Que símbolo escrever;
• Como mover o cabeçote ( para esquerda e para direita);
• Qual será seu novo estado, dados o símbolo que ele acabou de ler na fita e o estado em que se encontra.
• Se não houver entrada alguma na tabela para a combinação atual de símbolo e estado então a máquina pára.

• A quantidade de fita potencialmente ilimitada:
– Quantidade ilimitada de espaço de armazenamento.

Modelo de Von Neumann
• Proposto por volta de 1944-1945;
• Determina que programas também devem ser armazenados na memória:
– Primeiros