Se houver um problema que uma máquina de Turing não consiga resolver, nenhum algoritmo pode aplicar a solução. Essa conclusão parte do conceito de decidibilidade da máquina de Turing e promove a pesquisa e a determinação de problemas solucionáveis. Portanto, considere as seguintes afirmações sobre computabilidade e decidibilidade. Qual alternativa apresenta somente afirmações corretas?
Uma Máquina de Turing com múltiplas fitas possui o mesmo poder computacional de uma Máquina de Turing de fita única, sendo capaz de reconhecer exatamente a mesma classe de linguagens. É possível simular o comportamento de uma máquina com múltiplas fitas em uma máquina de fita única através do uso de símbolos auxiliares. À respeito dessas asserções, assinale a opção correta:
Considere um autômato finito determinístico (AFD) com as transições indicadas na figura. Qual das alternativas abaixo representa corretamente a linguagem formal aceita por esse autômato?
