Richardson-tétel

A matematikában a Richardson-tétel megmutatja, milyen mértékben döntheti el egy algoritmus, hogy bizonyos matematikai kifejezések egyenlőek.

A tétel szerint a kifejezések egy bizonyos osztályára eldönthetetlen, hogy egy adott E kifejezés kielégíti-e az E = 0 egyenletet, és hasonlóan meghatározhatatlan, hogy az E, illetve F kifejezéssel meghatározott függvények mindenhol azonosak-e.

Ezt az állítást Daniel Richardson angol számítógéptudós bizonyította be 1968-ban a bath-i egyetemen (Anglia).

A tétel azokra a kifejezésekre igaz, melyek a racionális számok, a π szám, a ln 2, az x változó, az összeadás, kivonás, szorzás, függvényösszetétel műveletek, valamint a szinuszfüggvény, exponenciális függvény és abszolútérték-függvény segítségével épülnek fel.

Léteznek olyan, a fentiektől eltérő kifejezésosztályok, amelyekre algoritmikus úton eldönthető, hogy a kifejezés lehet-e zéró.

Tétel

A Richardson-tétel a következőt állítja: Legyen E egy valós függvényhalmaz, úgy, hogy ha A(x) és B(x) ∈ E, akkor A(x) ± B(x), A(x)B(x), A(B(x)) ∈ E. A racionális számok mint konstans függvények szerepelnek E-ben. Ekkor ha A(x) egy kifejezés E-ben, akkor

• ha ln 2, π, e^x, sin x ∈ E, akkor az A(x) ≥ 0 minden x-re megoldhatatlan;
• ha |x| ∈ E akkor A(x) = 0 megoldhatatlan.

Továbbmenve, ha van egy B(x) ∈ E függvény, amelynek nincs primitív függvénye E-ben, akkor a függvény nem integrálható. Például $e^{ax^{2}}$ akkor és csak akkor rendelkezik elemi primitív függvénnyel, ha a =0.

Irodalom

• Richardson, Daniel: "Some unsolvable problems involving elementary functions of a real variable". (hely nélkül): Journal of Symbolic Logic. 1996.  
• http://mathworld.wolfram.com/RichardsonsTheorem.html
• http://dl.acm.org/citation.cfm?id=190429