Mortalidade (teoria da computabilidade)

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Question book.svg
Este artigo ou secção não cita fontes confiáveis e independentes (desde julho de 2016). Ajude a inserir referências.
O conteúdo não verificável pode ser removido.—Encontre fontes: Google (notícias, livros e acadêmico)

Na teoria da computabilidade, o problema da mortalidade é um problema de decisão que pode ser enunciado como segue:

Dada uma máquina de Turing, decidir se pára quando executada em uma configuração qualquer (não necessariamente uma configuração inicial)

Na declaração acima, a configuração é um par <q, w>, onde q é um dos estados da máquina (não necessariamente seu estado inicial) e w é uma sequência infinita de símbolos que representam o conteúdo inicial da fita. Note-se que enquanto geralmente assumimos que na configuração inicial quase todo número finito de células na fita são espaços em branco, no problema da mortalidade a fita pode ter conteúdo arbitrário, incluindo um número infinito de símbolos que não estão com o símbolo "em branco" escrito nela.

Philip K. Hooper provou em 1966 que o problema da mortalidade é indecidível. No entanto, pode-se mostrar que o conjunto de máquinas de Turing que são mortais (ou seja, que param em todas as configurações iniciais) é recursivamente enumerável.

Ícone de esboço Este artigo sobre computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.