제한된 기능에 대한 기능 일치

Question

기능 equality에 대한 질문을 게시했습니다. 신속하게 일반 기능 평등은 엄청나게 어려운 문제이며 수학적으로 파생 될 수 있다고 결론지었습니다.

내가 함수

f & g

function equal(f, g, domain) { 

} 

을 스텁하고자하는 하나 개의 인수를 정지 기능입니다. 그들의 논증은 자연수입니다. 이 함수는 부울 값을 반환합니다.

도메인이 전달되지 않으면 도메인이 모든 자연수로 기본 설정되어 있다고 가정 할 수 있습니다.

domain의 구조는 equal 기능에 가장 편리합니다.

또 다른 중요한 사실은 f & g이 결정적이라는 것입니다. f(n)에 대해 동일한 부울 m을 일관되게 반환합니다.

당신은 f 및 g 항상 복귀 한 자신의 입력이 domain

질문 내에있는 오류로 인해 예외 또는 사고가 발생하지 않는 것을 가정 할 수는 언어 무신론자와의 구현에 대한 요구하고있다 equal 기능. 나는 SO가 더 이상이 장소에 적합한 지 여부는 확실하지 않습니다.

f & g에는 부작용이 없습니다. domain은 유한 할 필요는 없습니다.

Answer 1

아직 불가능합니다.

몇 가지 한정된 수의 입력에 대해 두 함수를 테스트하고 해당 입력에서 같음을 확인할 수 있습니다. 두 입력이 동일하지 않으면 두 함수가 동일하지 않습니다. 테스트 한 모든 경우에 동등한 경우 동일한 기능을 수행 할 수있는 가능성이 있지만 완전히 확신 할 수는 없습니다.

일반적으로 도메인이 작지 않은 한 가능한 모든 입력을 테스트하는 것은 불가능합니다. 도메인이 32 비트 정수이고 함수가 매우 빠르다면 가능한 모든 입력을 검사하는 것이 가능할 수도 있습니다.

Answer 2

나는 당신이 소스 코드 정적 분석을하지 않고 할 수있는 최선의 것으로 다음과 같은 생각이이 유한 할 도메인을 가정

function equal(f, g, domain) { 
    var n; 
    for (n in domain) { 
     if (f(domain[n]) != g(domain[n])) return false; 
    } 
    return true; 
} 

하는 것으로. 우리는 F하자 g을 구현하고 F와 G이 구현 그럼 라이스의의 값을 계산하는 수학적 함수일 경우

: 도메인에 한정되지 않으면

는 Rice's theorem 기존 그러한 알고리즘을 방지 정리에 따르면 f가 G를 계산하는지 아니면 g가 F를 계산하는지 결정하는 것은 불가능합니다. 이는 이들이 구현의 중요하지 않은 특성이기 때문입니다.

자세한 내용은 my answer to the previous question을 참조하십시오.

Answer 3

사용 사례에 따라 f & g에 대한 몇 가지 가정을 수행 할 수 있습니다. 어쩌면 당신의 경우에, 그것들을 해결할 수있는 특정 조건 하에서 적용 할 것입니다.

다른 경우에만 권장 할만한 것은 퍼지 테스트, 추상 구문 트리 또는 기타 표현입니다.