MAPA – ESOFT – TEORIA DA COMPUTAÇÃO – 51_2026

Nesta atividade M.A.P.A., você terá a oportunidade de articular conceitos teóricos essenciais da disciplina, relacionando-os a modelos formais de computação e refletindo sobre suas aplicações e limitações. A proposta busca consolidar seu aprendizado por meio de uma produção escrita fundamentada no livro da disciplina.

A Teoria da Computação é um campo fundamental da Ciência da Computação, pois investiga os limites do que pode ser computado, os modelos formais de computação e a eficiência dos algoritmos. Desde os fundamentos históricos da computação até os conceitos de Máquina de Turing, problemas decidíveis e indecidíveis e complexidade computacional, esses conhecimentos permitem compreender não apenas como os computadores funcionam, mas também quais problemas podem ou não ser resolvidos por meio de algoritmos.

Fonte: OLIVEIRA, R. Ca. de. Teoria da Computação. Florianópolis: Arqué, 2025.

Com base no contexto apresentado e no livro da disciplina, responda às seguintes alternativas:

a) Explique os fundamentos históricos da Teoria da Computação, destacando como esse campo contribuiu para o surgimento e a evolução dos computadores e do pensamento computacional.

b) Descreva a Máquina de Turing, explicando seu funcionamento básico, suas principais características e as razões pelas quais ela é considerada um modelo universal de computação.

c) Apresente o conceito de problemas decidíveis e indecidíveis, explicando o que caracteriza cada um e os motivos pelos quais existem problemas que não podem ser resolvidos por algoritmos.