리처드슨의 정리

수학에서 리처드슨의 정리는 알고리즘이 특정 수학 표현이 동일한지 여부를 결정할 수 있는 정도에 대한 한계를 설정한다.상당히 자연스런 특정 종류의 표현에 대해서는 특정 표현식 E가 E = 0 등식을 만족하는지 여부를 알 수 없으며, 마찬가지로 표현식 E와 F로 정의한 함수가 도처에 동일한지(사실 E = F는 E - F = 0인 경우에만 해당)를 알 수 없다고 명시하고 있다.1968년 배스 대학의 컴퓨터 과학자 대니얼 리처드슨에 의해 증명되었다.

구체적으로는 정리가 가지고 있는 표현의 등급은 합리적인 숫자에 의해 생성되는 것으로 숫자 π, 숫자 ln 2, 변수 x, 덧셈, 뺄셈, 곱셈, 구성, 죄, exp, 복근 기능 등이 있다.

일부 종류의 표현(리차드슨의 정리보다 다른 원시적 표현에 의해 생성됨)에는 표현이 0인지 여부를 결정할 수 있는 알고리즘이 존재한다.^[1]

정리명세서

리처드슨의 정리는 다음과 같이 진술할 수 있다.^[2]E를 $R{\displaystyle \mathbb{}}$→ ${\displaystyle R\mathbb{}}$ ${\$ 함수를$$ 나타내는 식 집합으로 합시다.E에 다음 식이 포함되어 있다고 가정합시다.

• x (ID 함수 실행)
• e^x (지수 함수를 계산함수)
• sin x (sin 함수)
• 모든 합리적인 숫자, ln 2, π (입력을 무시하고 주어진 숫자를 출력하는 상수함수)

E도 몇 가지 표준 운영 하에서 폐쇄된다고 가정합시다.구체적으로, A와 B가 E에 있을 경우, 다음 사항도 E에 있다고 가정한다.

• A + B(A와 B가 나타내는 함수의 점적 추가를 나타냄)
• A - B(점괘 감산을 나타냄)
• AB(점수 곱셈을 나타냄)
• A∘B (A와 B로 대표되는 기능의 구성을 나타냄)

그러면 다음과 같은 의사결정 문제를 해결할 수 없다.

• E에서 표현 A가 모든 곳에서 음이 아닌 함수를 나타내는지 여부 결정
• E에 x(절대값 함수를 나타냄)라는 표현식도 포함하면, E의 표현식 A가 모든 곳에 0인 함수를 나타내는지 여부를 결정한다.
• E가 E에 대표성이 없는 함수를 나타내는 B를 포함하는 경우, E에 있는 A라는 표현식이 E로 대표될 수 있는 함수를 나타내는지를 결정한다(예: ${\displaystyle {{}^{}}^{}}$ ${\displaystyle {{x\mathrm{}}^{}}^{}}$ 2 ${\$ e$^{ax^{2}}:$ a = 0인 경우에만)

확장

1970년 힐버트의 10번째 문제가 해결된 후 B.F. Cavity는^x e와 ln 2의 사용이 제거될 수 있다는 것을 관찰했다.^[3]P. S. Wang은 나중에 A(x) < 0이 있는 x가 있는지 여부에 대한 의문이 풀릴 수 없는 동일한 가정 하에서, A(x) = 0이 있는 x가 있는지 여부에 대한 질문도 풀 수 없다고 언급했다.^[4]

미클로스 라츠코비치는 π의 필요성도 없앴고 작곡의 사용도 줄였다.^[5]특히 정수, x, sin xⁿ, sin(x sin xⁿ) 및 sin(x sin x)에 의해 생성된 링에 A(x)라는 표현식을 부여하면, 일부 x에 대해서는 A(x)가 0보다 0인지, 일부 x에 대해서는 A(x) = 0을 확인할 수 없는지에 대한 질문 둘 다 있다.

이와는 대조적으로 타르스키-세이덴버그 정리는 실장의 1차 이론은 해독이 가능하기 때문에 사인함수를 완전히 제거할 수는 없다고 말하고 있다.

참고 항목

• 상수 문제

참조

추가 읽기

• Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron (1996). A = B. A. K. Peters. p. 212. ISBN 1-56881-063-6. Archived from the original on 2006-01-29.

외부 링크

• Weisstein, Eric W. "Richardson's theorem". MathWorld.