É possível provar que uma função é idempotente?

12

É possível usar tipos estáticos ou dependentes para provar que uma função é idempotente?

Pesquisei no Google e em vários lugares no StackOverflow / StackExchange em busca de respostas sem sorte. O mais próximo que encontrei foi essa conversa sobre Idris: https://groups.google.com/forum/#!topic/idris-lang/yp7vrspChRg

Infelizmente, essa discussão está um pouco acima da minha cabeça.

haskell bmaddy
fonte
3
Não estou postando isso como resposta porque não tenho 100% de certeza, mas acredito que isso é impossível devido ao Teorema de Rice .
gardenhead
4
Essa é uma pergunta fascinante, e minha intuição indica que isso deve ser possível em uma linguagem restrita e não completa de Turing. No entanto, os programadores se concentram nas perguntas relacionadas ao ciclo de vida de desenvolvimento de software (consulte o centro de ajuda para obter detalhes), enquanto isso parece ser uma questão de ciência da computação. O site de Ciência da Computação pode se encaixar melhor e levar a melhores respostas.
amon
2
@gardenhead O teorema de Rice afirma que, dada qualquer propriedade que o comportamento de um programa possa ter, às vezes é impossível determinar se um programa tem ou não essa propriedade. Há uma grande diferença entre "isso às vezes é impossível" e "isso é impossível".
Tanner Swett
2
Meu último comentário foi bastante vago. De qualquer forma, eis o que o teorema de Rice tem a dizer: não existe um algoritmo que classifique corretamente todas as funções como idempotentes ou não. No entanto, ainda existem algoritmos úteis que classificam algumas funções como idempotentes ou não.
quer
2
O OP perguntou sobre provar que uma função é idempotente, não tendo um algoritmo classificando funções como idemptotentes ou não. A principal diferença é que uma prova pode ser escrita por uma pessoa. Quanto à integridade de Turing, de fato não é um problema .
Gallais

Respostas:

3

Para certas funções, é. Especialmente quando você conhece a função ;-)

Se você quer dizer com sua pergunta "existe um algoritmo para decidir automaticamente se uma função arbitrária é idempotente ou não", a resposta é não, devido aos teoremas já mencionados nos comentários. No entanto, para classes específicas de funções, pode-se - em teoria - decidir com muita facilidade se a função é idempotente ou não. Por exemplo, se a função é pura (significa: sem efeitos colaterais) e se sabe que sempre retorna um valor em uma quantidade finita de tempo para qualquer entrada, a idempotência pode ser decidida simplesmente tentando se f(f(x))=f(x)existe alguma entrada possível xpara a função. Não que isso seja muito eficiente, ele pode durar até o fim do universo.

Portanto, se essa não é a resposta que você estava procurando, escreva uma pergunta melhor, atualmente não está claro o que exatamente você está procurando.

Doc Brown
fonte
Obrigado pela resposta. A capacidade de "decidir automaticamente" era exatamente o que eu estava procurando.
bmaddy
2
Para expandir a declaração 'para determinadas funções, é' : a idempotência pode ser comprovada para qualquer função que aceite apenas uma quantidade finita de entradas (testando todas elas) ou um tipo de entrada definido recursivamente (como natural números ou listas vinculadas), o que significa que você só precisa provar que a idempotência é verdadeira para os casos base e os casos recursivos.
Qqwy