O termo inversão de programa tem várias tonalidades de significado, mas provavelmente começou com o trabalho de J. McCarthy, de 1956, The Inversion of Functions Defined by Turing Machines no contexto da IA. Até agora, muitas conexões entre inversão de programa e outros campos foram descobertas, por exemplo, programação reversível (física e lógica), avaliação parcial, verificação, programação bidirecional, programação lógica e aprendizado de máquina.
O que é inversão de programa? Em primeira aproximação é algo assim: Dado um programa tomando argumentos do tipo A e retornando resultados do tipo B , produzir um programa P - 1 que é "de alguma forma" o inverso de P . Estou deliberadamente sendo vago aqui, já que o conceito pode ser (e é) esclarecido de várias maneiras: por exemplo, é necessário que P seja injetor? Should P - 1 ( b ) devolver todos ou apenas alguns de uma forma que P ( a ) = b?
Existem maneiras genéricas de inverter um programa, por exemplo, usando a diagonalização, como já indicado por McCarthy, ou usando a avaliação parcial, mas elas tendem a não ser eficientes. Além disso, a maioria dos trabalhos sobre inversão de programas com os quais estou familiarizado não parece lidar com linguagens de programação completas de ordem superior (ou seja, -calculi).
Solicitação de referência. Qual é o estado da arte em algoritmos explícitos para inversão de programa de calculi (sem restrição de ordem superior)?