A redução do problema de parada é uma ferramenta poderosa para provar que um determinado problema (ou algoritmo) é indecidível , o que significa que não há algoritmo geral que sempre possa determinar corretamente se a instância do problema fornecida pode ser resolvida por algum outro algoritmo. * Não * diz diretamente se um algoritmo * é * computável, mas se determinar * uma propriedade sobre * o algoritmo é computável.

Veja como funciona a redução:

1. Compreendendo o problema de interrupção:

*O problema de parada pergunta:Dado um algoritmo (programa) *h *e uma entrada *i *para esse algoritmo, irá *h *halt (terminar em execução) quando executado com entrada *i *?
* O problema de parada é indecidível . Não há algoritmo, `interrompa (h, i)`, que sempre pode retornar corretamente `true` se *h *parar *i *e` false` se *h *loops para sempre.

2. A técnica de redução (prova por contradição):

Para provar que um problema * p * é indecidível, você faz o seguinte:

1. Suponha, por uma questão de contradição, que * p * é decidível. Isso significa que assumimos que existe um algoritmo `solvep (inputForp)` que sempre retorna corretamente a solução para qualquer instância do problema *p *.

2. Construa uma redução: Você precisa mostrar como usar o hipotético algoritmo `solvep ()` para resolver o problema de interrupção. Em outras palavras, você cria um algoritmo `parada (h, i)` que usa `solvep ()` como uma sub -rotina. Este algoritmo `interrompe (h, i)` deve funcionar da seguinte forma:

`` `
parada (h, i):
1. Transforme a instância do problema de interrupção (h, i) em uma instância do problema P, vamos chamá -lo de 'inputForp`. Esta é a etapa crucial:você está criando `inputForp` de uma maneira que *a solução para o problema P nessa entrada revela diretamente se H é interrompido em i *. As especificidades de como você faz essa transformação dependem inteiramente do problema *p *.
2. ResultP =Solvep (InputForp) // Chame nosso solucionador hipotético para o problema P.
3. Com base no resultado, determine se H interrompe em i e retorne verdadeiro ou falso de acordo.
`` `

3. Mostre que sua redução implica uma solução para o problema de interrupção: Explique claramente como o resultado de `solvep (inputForp)` diz diretamente se o algoritmo *h *é interrompido na entrada *i *.

4. contradição: Como o problema de interrupção é conhecido por ser indecidível e você mostrou que um hipotético `solvep` poderia ser usado para resolvê -lo, você alcançou uma contradição.

5. Conclusão: Portanto, nossa suposição inicial (de que * p * é decidível) deve ser falsa. Portanto, o problema * p * é indecidível.

Idéias e desafios -chave:

* a transformação é chave: A parte mais difícil é encontrar uma transformação de (h, i) para uma instância de *p *, de modo que a solução para *p *revele diretamente se *h *interrompe *i *. Isso requer inteligência e compreensão do problema de parada e do problema *p *.
* Prova por contradição: Você não está * diretamente * provando que * p * é indecidível. Você está mostrando que, se * p * * fosse * decidível, isso levaria a uma impossibilidade (resolvendo o problema de interrupção).
* Generalização: O objetivo é provar que *não pode *existir um algoritmo que resolve *p *para *todas as entradas possíveis *. Sua redução deve ser válida para qualquer algoritmo arbitrário *h *e entrada *i *.

Exemplo:o problema do vazio para as máquinas Turing

O problema do vazio para as máquinas Turing pergunta:Dada uma máquina de Turing *M *, o idioma é aceito por *m *vazio (ou seja, *m *aceita *alguma *entrada)? Vamos mostrar que isso é indecidente.

1. Suponha que o vazio seja decidível: Suponha que haja um algoritmo `isEmpty (m)` que retorna `true` se o idioma aceito por * m * estiver vazio e` falso`.

2. Redução: Criaremos um algoritmo `parada (h, i)` que usa `isEmpty ()`:

`` `
parada (h, i):
1. // Construa uma nova máquina de Turing M_HI
// - m_hi recebe qualquer entrada w.
// - m_hi primeiro simula h em I.
// - Se h interromper em i, então m_hi aceita w.
// - Se h não parar em i, então m_hi loops para sempre.
M_hi =constructtm (h, i)

2. Resultado =isEmpty (m_hi)

3. Se resultado ==true:
retornar false // h não pára em i
outro:
Retorne True // H interrompe em i
`` `

3. Por que isso funciona:

*Se *h *interromper *i *, então `m_hi` aceitará *cada *entrada` W`. Assim, o idioma aceito por `m_hi` não está vazio (na verdade é σ*, o conjunto de todas as cordas). Portanto, `isEmpty (m_hi)` retornará `false`, e` interrompa (h, i) `retorna 'true`.

*Se *h *não *param *i *, então `m_hi` fará um loop para sempre em *todas as *entradas` w`. Assim, o idioma aceito por `m_hi` está vazio. Portanto, `isEmpty (m_hi)` retornará `true` e` interrompa (h, i) `retorna 'false`.

4. contradição: Criamos um algoritmo `parado (h, i)` que usa `isEmpty ()` para resolver o problema de parada. Mas o problema de interrupção é indecidível, então isso é uma contradição.

5. Conclusão: Portanto, o problema do vazio para as máquinas de Turing é indecidível.

Notas importantes:

* A redução mostra que o problema * p * é * pelo menos tão difícil quanto * o problema de parada. Como o problema de interrupção é indecidível, o mesmo acontece com *p *.
* Reduções são frequentemente usadas para provar indecidibilidade, mas também podem ser usadas para provar a completude NP no contexto da complexidade computacional.
* O algoritmo `construttm (h, i)` no exemplo acima é um construto teórico. Na prática, você não "construiria" uma máquina de Turing física. O ponto é que * em princípio * é possível descrever essa máquina.

Em resumo, a redução de problemas de interrupção é uma técnica de prova poderosa que nos ajuda a entender os limites da computação. Ao mostrar que resolver um problema específico implicaria uma solução para o problema de parada (o que sabemos que é impossível), podemos concluir que o problema é indecidente.