Máquina de Turing

Conceitos em Ciência da Computação

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

De Autômatos a Máquinas de Turing

  • Autômato Finito: Memória limitada; lida com linguagens regulares.
  • Autômato com Pilha: Memória em pilha; lida com linguagens livres de contexto.
  • Máquina de Turing: Memória ilimitada (fita infinita); resolve todos os problemas computáveis.

Uma ilustração de Alan Turing

Conceitos em Ciência da Computação

O que é uma Máquina de Turing?

Um diagrama que mostra como uma Máquina de Turing funciona

Máquina de Turing

  • Máquina abstrata com fita infinita.
  • Lê e escreve símbolos.
  • Consegue simular qualquer algoritmo.
Conceitos em Ciência da Computação

Máquinas de Turing por analogia

Uma ilustração de uma cozinha com um cozinheiro seguindo uma receita como analogia de uma Máquina de Turing

Cozinha e cozinheiro como Máquina de Turing

  • O balcão é a fita.
  • As seções do balcão são as células.
  • Os ingredientes são os símbolos.
  • O cozinheiro é a cabeça que lê e escreve.
  • O livro de receitas é o programa que guia todo o processo.
Conceitos em Ciência da Computação

Por que a Máquina de Turing é importante?

Máquina de Turing e Computabilidade

  • Consegue simular qualquer algoritmo
  • Define o limite do que computadores conseguem resolver
  • Introduz problemas indecidíveis (ex.: Problema da Parada)
  • Base da teoria da computação moderna
Conceitos em Ciência da Computação

O Problema da Parada

  • A pergunta: Dá para prever se um programa vai parar ou rodar para sempre para uma entrada?
  • Saque do Turing: Não existe algoritmo universal que resolva isso para todos os programas.
  • Resultado: O Problema da Parada é indecidível; alguns problemas não têm solução algorítmica.
  • Impactos: Limites da computação afetam criptografia e IA

Um diagrama que mostra o que é o Problema da Parada

Conceitos em Ciência da Computação

Vamos praticar!

Conceitos em Ciência da Computação

Preparing Video For Download...