Richardsonova věta - Richardsons theorem - Wikipedia

V matematice Richardsonova věta stanoví omezení rozsahu, v jakém algoritmus umět rozhodni se zda jsou určité matematické výrazy stejné. Uvádí, že pro určitou docela přirozenou třídu výrazů ano nerozhodnutelný zda konkrétní výraz E splňuje rovnici E = 0 a podobně nerozhodnutelné, zda jsou funkce definované výrazy E a F jsou si všude rovni (ve skutečnosti E = F kdyby a jen kdyby E − F = 0). V roce 1968 to dokázal počítačový vědec Daniel Richardson z University of Bath.

Konkrétně třída výrazů, pro které platí věta, je ta, která je generována racionálními čísly, číslem π, číslo ln 2 proměnná Xoperace sčítání, odčítání, násobení, složení a hřích, exp, a břišní svaly funkce.

Pro některé třídy výrazů (generovaných jinými primitivy než v Richardsonově teorému) existují algoritmy, které mohou určit, zda je výraz nula.[1]

Výrok věty

Richardsonovu větu lze konstatovat následovně:[2] Nechat E být množinou výrazů, které představují ℝ → ℝ funkce. Předpokládejme to E zahrnuje tyto výrazy:

  • X (představující funkci identity)
  • EX (představující exponenciální funkce)
  • hřích X (představující funkci hříchu)
  • všechna racionální čísla, ln 2 a π (představující konstantní funkce, které ignorují jejich vstup a produkují dané číslo jako výstup)

Předpokládat E je také uzavřen v rámci několika standardních operací. Konkrétně předpokládejme, že pokud A a B jsou v E, pak jsou všechny následující položky také v E:

  • A + B (představující bodové přidání funkcí, které A a B zastupovat)
  • A – B (představující bodové odčítání)
  • AB (představující bodové násobení)
  • A∘B (představující složení funkcí představovaných znakem A a B)

Pak následující rozhodovací problémy jsou neřešitelné:

  • Rozhodování, zda výraz A v E představuje funkci, která není všude záporná
  • Li E zahrnuje také výraz |X| (představující funkci absolutní hodnoty), rozhodování, zda výraz A v E představuje funkci, která je všude nulová
  • Li E zahrnuje výraz B představující funkci, jejíž primitivní nemá zástupce v E, rozhodování, zda výraz A v E představuje funkci, jejíž primitivní funkci lze reprezentovat E. (Příklad: má ve hře antihmotivum základní funkce kdyby a jen kdyby A = 0.)

Rozšíření

Po Hilbertův desátý problém byl vyřešen v roce 1970, B. F. Caviness poznamenal, že použití EX a ln 2 mohl být odstraněn.[3]P. S. Wang později poznamenal, že za stejných předpokladů, za kterých byla otázka, zda existuje X s A(X) <0 byla nerozpustná, otázka, zda ano X s A(X) = 0 byl také nerozpustný.[4]

Miklós Laczkovich odstranila také potřebu π a omezila použití kompozice.[5] Zejména vzhledem k výrazu A(X) v kruhu generovaném celými čísly, X, hřích Xna hřích (X hříchXn), jak otázka, zda A(X)> 0 pro některé X a zda A(X) = 0 pro některé X jsou neřešitelné.

Naproti tomu Věta Tarski – Seidenberg říká, že teorie prvního řádu reálného pole je rozhodnutelná, takže není možné zcela odstranit sinusovou funkci.

Viz také

Reference

  1. ^ Dan Richardson a John Fitch, 1994, "Problém identity pro základní funkce a konstanty ", Proceedings of the international symposium on Symbolic and algebraic computation, pp. 85–290.
  2. ^ Richardson, Daniel (1968). "Některé nerozhodnutelné problémy spojené se základními funkcemi skutečné proměnné". Journal of Symbolic Logic. 33 (4): 514–520. JSTOR  2271358. Zbl  0175.27404.
  3. ^ Caviness, B. F. (1970). "O kanonických formulářích a zjednodušení". Deník ACM. 17 (2): 385–396. doi:10.1145/321574.321591.
  4. ^ Wang, P. S. (1974). "Nerozhodnutelnost existence nul skutečných elementárních funkcí". Časopis Asociace pro výpočetní techniku. 21 (4): 586–589. doi:10.1145/321850.321856.
  5. ^ Laczkovich, Miklós (2003). „Odstranění π z některých nerozhodnutelných problémů týkajících se základních funkcí“. Proc. Amer. Matematika. Soc. 131 (7): 2235–2240. doi:10.1090 / S0002-9939-02-06753-9.

Další čtení

externí odkazy