Se você tem duas funções implementando um algoritmo de classificação diferente, é possível inferir pelo código-fonte que ambas possuem as mesmas propriedades externas? Significando que ambos terão uma sequência não classificada possível como entrada e uma sequência classificada como saída? De que maneira essas propriedades externas podem ser determinadas pelo código fonte? E como você descreveria essas propriedades externas? Que notação seria usada?
As propriedades externas podem ser conhecidas, definindo-as explicitamente, por exemplo, dentro de um sistema de tipos, mas estou imaginando se isso poderia ser feito implicitamente. Ou é de alguma forma teoricamente impossível inferir esse tipo de semântica? Estou interessado em saber se isso é possível para funções arbitrárias, não apenas para algoritmos de classificação, assumindo que coisas como funções sempre parem e não tenham efeitos colaterais.
Devo olhar para a semântica denotacional ou não está relacionada?
Estou interessado em indicadores para pesquisar nesta área e em termos diferentes usados para descrever o assunto que pode ajudar na minha pesquisa bibliográfica.
fonte
A igualdade extensional em Turing linguagens de programação completas é indecidível em geral, mas isso não deve impedir você de verificar ou falsificar se duas funções específicas são extensionalmente iguais.
fonte
Uma resposta rápida (admito que não gastei muito tempo ...) O teorema de Rice diz que, para qualquer questão não trivial, é indecidível dizer se a função calculada por um programa terá a propriedade ou não. Portanto, a questão aqui é indecidível
fonte