Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação. Marque a opção que representa um Problema incomputável.

A. Encontrar os anos bissextos.
B. Decriptação.
C. Somar todos os números primos entre 1 e 100, inclusive.
D. Rota mais curta em um mapa.
E. Encontrar todos os erros de um programa computacional.

Question

Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação. Marque a opção que representa um Problema incomputável.

A. Encontrar os anos bissextos.
B. Decriptação.
C. Somar todos os números primos entre 1 e 100, inclusive.
D. Rota mais curta em um mapa.
E. Encontrar todos os erros de um programa computacional.

Accepted Answer

Para resolver essa questão, vamos analisar as opções e identificar qual delas representa um problema incomputável.

A computabilidade é a habilidade de resolver problemas de forma efetiva. Um problema é considerado incomputável se não há algoritmo que possa resolvê-lo para todos os casos possíveis.

Vamos analisar cada alternativa:

A) Encontrar os anos bissextos - Este é um problema computável, pois há uma regra clara para determinar anos bissextos.

B) Decriptação - A decriptação em si pode ser computável, mas depende do contexto e do método de criptografia.

C) Somar todos os números primos entre 1 e 100, inclusive - Este é um problema computável, pois podemos listar e somar esses números.

D) Rota mais curta em um mapa - Este é um problema computável, conhecido como o problema do caminho mínimo, que pode ser resolvido por algoritmos como Dijkstra.

E) Encontrar todos os erros de um programa computacional - Este é um problema incomputável, conhecido como o problema da parada, que afirma que não há algoritmo geral para determinar se um programa arbitrário termina ou entra em loop infinito.

**Resposta: E**

Encontrar todos os erros de um programa computacional é um exemplo de problema incomputável.