Presburgerova aritmetika - Presburger arithmetic

Presburgerova aritmetika je teorie prvního řádu z přirozených čísel s přidáním , pojmenovaný na počest Mojżesz Presburgerova , který ji představil v roce 1929. Podpis of presburgerova aritmetika je pouze operace sčítání a rovnosti , s vynecháním násobení provoz úplně. Axiomy zahrnují schéma indukce .

Presburgerova aritmetika je mnohem slabší než aritmetika Peano , která zahrnuje operace sčítání i násobení. Na rozdíl od Peanoovy aritmetiky je Presburgerova aritmetika rozhodovatelnou teorií . To znamená, že je možné u jakékoli věty v jazyce Presburgerovy aritmetiky algoritmicky určit, zda je tato věta prokazatelná z axiomů Presburgerovy aritmetiky. Asymptotická výpočetní složitost tohoto algoritmu za běhu je alespoň dvojnásobně exponenciální , jak ukazuje Fischer a Rabin (1974) .

Přehled

Jazyk Presburgerovy aritmetiky obsahuje konstanty 0 a 1 a binární funkci +, interpretovanou jako sčítání.

V tomto jazyce jsou axiomy Presburgerovy aritmetiky univerzálními uzávěry následujících:

¬ (0 = x + 1)
x + 1 = y + 1 → x = y
x + 0 = x
x + ( y + 1) = ( x + y ) + 1
Nechť P ( x ) je vzorec prvního řádu v jazyce Presburgerovy aritmetiky s volnou proměnnou x (a případně dalšími volnými proměnnými). Pak je následující vzorec axiom:
( P (0) ∧ ∀ x ( P ( x ) → P ( x + 1))) → ∀ y P ( y ).

(5) je schéma axióma z indukce , což představuje nekonečně mnoho axiómy. Ty nelze nahradit žádným konečným počtem axiomů, to znamená, že Presburgerova aritmetika není v logice prvního řádu konečně axiomatizovatelná.

Na Presburgerovu aritmetiku lze pohlížet jako na teorii prvního řádu s rovností obsahující přesně všechny důsledky výše uvedených axiomů. Alternativně jej lze definovat jako sadu vět, které jsou pravdivé v zamýšlené interpretaci : struktura nezáporných celých čísel s konstantami 0, 1 a sčítání nezáporných celých čísel.

Aritmetika Presburger je navržena tak, aby byla úplná a rozhodnutelná. Proto nemůže formalizovat pojmy jako dělitelnost nebo prvenství , nebo obecněji jakýkoli číselný koncept vedoucí k násobení proměnných. Může však formulovat jednotlivé instance dělitelnosti; například dokazuje „pro všechna x existuje y : ( y + y = x ) ∨ ( y + y + 1 = x )“. To znamená, že každé číslo je sudé nebo liché.

Vlastnosti

Mojżesz Presburger dokázal, že Presburgerova aritmetika je:

konzistentní : V Presburgerově aritmetice neexistuje tvrzení, které by bylo možné odvodit z axiomů tak, aby bylo možné odvodit i jeho negaci.
kompletní : Pro každé tvrzení v jazyce Presburgerovy aritmetiky je buď možné jej odvodit z axiomů, nebo je možné odvodit jeho negaci.
rozhodnutelné : Existuje algoritmus, který rozhoduje, zda je dané tvrzení v Presburgerově aritmetice větou nebo ne -větou.

Rozhodovatelnost Presburgerovy aritmetiky lze ukázat pomocí eliminace kvantifikátoru , doplněnou úvahami o aritmetické shodě ( Presburger (1929) , Nipkow (2010) , Enderton 2001, s. 188). Kroky použité k ospravedlnění algoritmu eliminace kvantifikátoru lze použít k definování rekurzivních axiomatizací, které nemusí nutně obsahovat axiomové schéma indukce ( Presburger (1929) , Stansifer (1984) ).

Naproti tomu Peanoova aritmetika , což je Presburgerova aritmetika rozšířená o násobení, není rozhodnutelná, v důsledku negativní odpovědi na problém Entscheidungsproblem . Podle Gödelovy věty o neúplnosti je Peanoova aritmetika neúplná a její konzistence není vnitřně prokazatelná (viz Gentzenův důkaz konzistence ).

Výpočetní náročnost

Rozhodovací problém pro Presburgerovu aritmetiku je zajímavým příkladem v teorii a výpočtu výpočetní složitosti . Nechť n je délka příkazu v Presburgerově aritmetice. Poté Fischer a Rabin (1974) dokázali, že v nejhorším případě má důkaz tvrzení v logice prvního řádu alespoň délku , pro nějakou konstantu c > 0. Proto jejich rozhodovací algoritmus pro Presburgerovu aritmetiku má dobu běhu alespoň exponenciální. Fischer a Rabin také dokázali, že pro jakoukoli rozumnou axiomatizaci (přesně definovanou v jejich článku) existují věty o délce n, které mají dvojnásobně exponenciální důkaz délky. Intuitivně to naznačuje, že existují výpočetní limity toho, co lze dokázat počítačovými programy. Fischerova a Rabinova práce také znamená, že Presburgerovu aritmetiku lze použít k definování vzorců, které správně vypočítají jakýkoli algoritmus, pokud jsou vstupy menší než relativně velké hranice. Hranice lze zvýšit, ale pouze pomocí nových vzorců. Oppen (1978) naopak prokázal trojnásobně exponenciální horní hranici rozhodovacího postupu pro Presburgerovu aritmetiku. ${\ displaystyle 2^{2^{cn}}}$

Těsnější hranice složitosti byla ukázána pomocí střídajících se tříd složitosti podle Bermana (1980) . Sada pravdivých tvrzení v Presburgerově aritmetice (PA) je zobrazena jako kompletní pro TimeAlternations (2 ^{2 ^{n ^{O (1)}}} , n). Jeho složitost je tedy mezi dvojitým exponenciálním nedeterministickým časem (2-NEXP) a dvojitým exponenciálním prostorem (2-EXPSPACE). Úplnost je v polynomiálním čase redukce mnoho ku jedné. (Všimněte si také, že zatímco Presburgerova aritmetika je běžně zkrácena PA, v matematice obecně PA obvykle znamená Peanoovu aritmetiku .)

Pro jemnější zrnitost nechť PA (i) je množina pravdivých Σ _i PA prohlášení a PA (i, j) sada pravdivých Σ _i PA prohlášení s každým blokem kvantifikátoru omezeným na j proměnných. '<' je považován za bez kvantifikátoru; zde jsou omezené kvantifikátory počítány jako kvantifikátory.
PA (1, j) je v P, zatímco PA (1) je NP-kompletní.
Pro i> 0 a j> 2 je PA (i + 1, j) Σ _i^P -kompletní . Výsledek tvrdosti potřebuje pouze j> 2 (na rozdíl od j = 1) v posledním bloku kvantifikátoru.
Pro i> 0 je PA (i+1) Σ _i^EXP -kompletní (a je TimeAlternations (2 ^{n ^{O (i)}} , i) -kompletní).

Aplikace

Protože Presburgerova aritmetika je rozhodnutelná, existují automatické ověřovače teorém pro Presburgerovu aritmetiku. Například systém Coq proof assistant má taktickou omegu pro aritmetiku Presburger a Isabelle proof assistant obsahuje ověřený postup eliminace kvantifikátoru od Nipkow (2010) . Díky dvojí exponenciální složitosti teorie není možné použít na složitých vzorcích dokazovače teorémů, ale k tomuto chování dochází pouze za přítomnosti vnořených kvantifikátorů: Oppen a Nelson (1980) popisují automatický důkaz věty, který používá simplexový algoritmus na rozšířeném Presburgerova aritmetika bez vnořených kvantifikátorů k prokázání některých instancí Presburgerových aritmetických vzorců bez kvantifikátorů. Novější řešitelé modulárních teorií uspokojivosti využívají úplných celočíselných programovacích technik ke zpracování fragmentu Presburgerovy aritmetické teorie bez kvantifikátoru ( King, Barrett & Tinelli (2014) ).

Presburgerovu aritmetiku lze rozšířit o násobení konstantami, protože násobení je opakované sčítání. Většina výpočtů dolního indexu pole pak spadá do oblasti rozhodnutelných problémů. Tento přístup je základem nejméně pěti systémů kontroly správnosti počítačových programů , počínaje ověřovatelem Stanford Pascal na konci sedmdesátých let a pokračuje až do systému Microsoft Spec# z roku 2005.

Celočíselný vztah definovatelný Presburgerem

Nyní jsou uvedeny některé vlastnosti týkající se celočíselných relací definovatelných v Presburgerově aritmetice. Kvůli jednoduchosti jsou všechny vztahy uvažované v této části nad nezápornými celými čísly.

Vztah je definovatelný Presburgerem pouze tehdy, je-li to semilineární množina .

Unární celočíselný vztah , tj. Sada nezáporných celých čísel, lze definovat Presburgerem právě tehdy, pokud je nakonec periodický. To znamená, že pokud existuje prahová hodnota a kladná perioda taková, že pro všechna celá čísla taková , že a pouze pokud . ${\ displaystyle R}$ ${\ displaystyle t \ in \ mathbb {N}}$ ${\ Displaystyle p \ in \ mathbb {N} ^{> 0}}$ ${\ displaystyle n}$ ${\ displaystyle | n | \ geq t}$ ${\ displaystyle n \ v R}$ ${\ displaystyle n+p \ v R}$

Podle Cobham – Semenovovy věty je vztah definovatelný Presburgerem právě tehdy, je-li definovatelný v Büchiho aritmetice základny pro všechny . Vztah definovatelná v Buchi aritmetice báze a pro a bytí multiplikativní nezávislá celá čísla je Presburgerova definovatelné. ${\ displaystyle k}$ ${\ Displaystyle k \ geq 2}$ ${\ displaystyle k}$ ${\ displaystyle k '}$ ${\ displaystyle k}$ ${\ displaystyle k '}$

Celočíselný vztah je definovatelný Presburgerem právě tehdy, pokud všechny sady celých čísel, které jsou definovatelné v logice prvního řádu s přidáním a (to znamená Presburgerova aritmetika plus predikát pro ), jsou definovatelné Presburgerem. Ekvivalentně pro každý vztah, který není definovatelný Presburgerem, existuje vzorec prvního řádu s přidáním a který definuje množinu celých čísel, která není definovatelná pouze pomocí sčítání. ${\ displaystyle R}$ ${\ displaystyle R}$ ${\ displaystyle R}$ ${\ displaystyle R}$ ${\ displaystyle R}$

Muchnikova charakteristika

Vztahy definovatelné Presburgerem připouštějí další charakteristiku: Muchnikovou větou. Uvedení je složitější, ale vedlo k prokázání dvou dřívějších charakteristik. Než bude možné vyslovit Muchnikovu větu, je třeba zavést některé další definice.

Dovolit být nastavena, část z pro a je definován jako ${\ Displaystyle R \ subseteq \ mathbb {N} ^{d}}$ ${\ displaystyle x_ {i} = j}$ ${\ displaystyle R}$ ${\ Displaystyle i <d}$ ${\ displaystyle j \ in \ mathbb {N}}$

{\ Displaystyle \ left \ {(x_ {0}, \ ldots, x_ {i-1}, x_ {i+1}, \ ldots, x_ {d-1}) \ in \ mathbb {N} ^{d -1} \ mid (x_ {0}, \ ldots, x_ {i-1}, j, x_ {i+1}, \ ldots, x_ {d-1}) \ in R \ right \}.}

Vzhledem ke dvěma sadám a -tuple celých čísel se tato sada nazývá -periodická v if, pro všechny takové, že pak tehdy a jen pokud . For , set je řekl, aby byl -periodic in if it is -periodic for some such that ${\ displaystyle R, S \ subseteq \ mathbb {N} ^{d}}$ ${\ displaystyle d}$ ${\ Displaystyle (p_ {0}, \ ldots, p_ {d-1}) \ in \ mathbb {N} ^{d}}$ ${\ displaystyle R}$ ${\ displaystyle (p_ {0}, \ dots, p_ {d-1})}$ ${\ displaystyle S}$ ${\ Displaystyle (x_ {0}, \ dots, x_ {d-1}) \ v S}$ ${\ Displaystyle (x_ {0}+p_ {0}, \ dots, x_ {d-1}+p_ {d-1}) \ v S,}$ ${\ Displaystyle (x_ {0}, \ ldots, x_ {d-1}) \ v R}$ ${\ Displaystyle (x_ {0}+p_ {0}, \ dots, x_ {d-1}+p_ {d-1}) \ v R}$ ${\ Displaystyle s \ in \ mathbb {N}}$ ${\ displaystyle R}$ ${\ displaystyle s}$ ${\ displaystyle S}$ ${\ displaystyle (p_ {0}, \ ldots, p_ {d-1})}$ ${\ Displaystyle (p_ {0}, \ dots, p_ {d-1}) \ in \ mathbb {Z} ^{d}}$

{\ Displaystyle \ sum _ {i = 0}^{d-1} | p_ {i} | <s.}

Nakonec pro let ${\ Displaystyle k, x_ {0}, \ dots, x_ {d-1} \ in \ mathbb {N}}$

{\ Displaystyle C (k, (x_ {0}, \ ldots, x_ {d-1})) = = left \ {(x_ {0}+c_ {0}, \ dots, x_ {d-1}+ c_ {d-1}) \ mid 0 \ leq c_ {i} <k \ right \}}

označte krychli velikosti, jejíž menší roh je . ${\ displaystyle k}$ ${\ displaystyle (x_ {0}, \ dots, x_ {d-1})}$

Muchnikova věta - je definovatelná Presburgerem pouze tehdy, pokud: ${\ Displaystyle R \ subseteq \ mathbb {N} ^{d}}$

pokud jsou pak všechny sekce definovány Presburgerem a ${\ Displaystyle d> 1}$ ${\ displaystyle R}$
existuje takové, že pro každého existuje takové, že pro všechny s ${\ Displaystyle s \ in \ mathbb {N}}$ ${\ displaystyle k \ in \ mathbb {N}}$ ${\ displaystyle t \ in \ mathbb {N}}$ ${\ Displaystyle (x_ {0}, \ dots, x_ {d-1}) \ in \ mathbb {N} ^{d}}$ ${\ Displaystyle \ sum _ {i = 0}^{d-1} x_ {i}> t,}$ ${\ displaystyle R}$ je -periodický v . ${\ displaystyle s}$ ${\ Displaystyle C (k, (x_ {0}, \ dots, x_ {d-1}))}$

Intuitivně celé číslo představuje délku posunu, celé číslo je velikost kostek a je prahovou hodnotou před periodicitou. Tento výsledek zůstává pravdivý i při splnění podmínky ${\ displaystyle s}$ ${\ displaystyle k}$ ${\ displaystyle t}$

{\ Displaystyle \ sum _ {i = 0}^{d-1} x_ {i}> t}

je nahrazeno buď nebo . ${\ Displaystyle \ min (x_ {0}, \ ldots, x_ {d-1})> t}$ ${\ Displaystyle \ max (x_ {0}, \ ldots, x_ {d-1})> t}$

Tato charakteristika vedla k takzvanému „definovatelnému kritériu definovatelnosti v Presburgerově aritmetice“, tj. Existuje vzorec prvního řádu s adicí a aaryálním predikátem, který platí tehdy a jen tehdy, je- li interpretován vztahem definovatelným Presburgerem. Muchnikova věta také umožňuje dokázat, že je možné rozhodnout, zda automatická sekvence přijímá množinu definovatelnou Presburgerem. ${\ displaystyle d}$ ${\ displaystyle R}$ ${\ displaystyle R}$

Viz také

Reference

Haase, Christoph (2018). „Průvodce přežitím do presburgerové aritmetiky“ . Zprávy ACM SIGLOG . 5 (3): 67–82. doi : 10,1145/3242953.3242964 . S2CID 51847374 .
Cooper, DC, 1972, „Věta dokazující v aritmetice bez násobení“ v B. Meltzer a D. Michie, eds., Machine Intelligence Vol. 7 . Edinburgh University Press: 91–99.
Enderton, Herbert (2001). Matematický úvod do logiky (2. vyd.). Boston, MA: Academic Press . ISBN 978-0-12-238452-3.
Ferrante, Jeanne a Charles W. Rackoff, 1979. Výpočetní složitost logických teorií . Přednášky z matematiky 718. Springer-Verlag .
Fischer, Michael J .; Rabin, Michael O. (1974). „Superexponenciální složitost Presburgerovy aritmetiky“ . Sborník příspěvků ze sympozia SIAM-AMS v aplikované matematice . 7 : 27–41. Archivovány od originálu na 2006-09-15 . Citováno 2006-06-11 .
G. Nelson a DC Oppen (duben 1978). „Zjednodušovač založený na efektivních rozhodovacích algoritmech“. Proč. 5. sympozium ACM SIGACT-SIGPLAN o principech programovacích jazyků : 141–150. doi : 10,1145/512760,512775 . S2CID 6342372 .
Presburger, Mojżesz (1929). „Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition ass einzige Operation hervortritt“. Comptes Rendus du I congrès de Mathématiciens des Pays Slaves, Warszawa : 92–101., viz anglický překlad Stansifer (1984)
Stansifer, Ryan (září 1984). Presburgerův článek o celočíselné aritmetice: Poznámky a překlad (PDF) (technická zpráva). TR84-639. Ithaca/NY: Katedra informatiky, Cornell University.
William Pugh , 1991, „ Test Omega: rychlý a praktický celočíselný programovací algoritmus pro analýzu závislosti “.
Reddy, CR a DW Loveland, 1978, „ Presburgerova aritmetika s alterací omezeného kvantifikátoru. “ Symposium ACM o teorii počítačů : 320–325.
Young, P., 1985, „Gödelovy věty, exponenciální obtížnost a nerozhodnutelnost aritmetických teorií: expozice“ v A. Nerode a R. Shore, The Recursion Theory, American Mathematical Society: 503-522.
Oppen, Derek C. (1978). „A 2 ^{2 ^{2 ^pn}} Upper Bound on the Complexity of Presburger Aritmetic“ . J. Comput. Syst. Sci . 16 (3): 323–332. doi : 10,1016/0022-0000 (78) 90021-1 .
Berman, L. (1980). „Složitost logických teorií“ . Teoretická počítačová věda . 11 (1): 71–77. doi : 10,1016/0304-3975 (80) 90037-7 .
Nipkow, T (2010). „Odstranění lineárního kvantifikátoru“ (PDF) . Journal of Automated Reasoning . 45 (2): 189–212. doi : 10,1007/s10817-010-9183-0 . S2CID 14279141 .
Král, Tim; Barrett, Clark W .; Tinelli, Cesare (2014). „Využití lineárního a smíšeného celočíselného programování pro SMT“. 2014 Formální metody v počítačem podporovaném designu (FMCAD) . 2014 . s. 139–146. doi : 10,1109/FMCAD.2014.6987606 . ISBN 978-0-9835-6784-4. S2CID 5542629 .

externí odkazy

Kompletní důkaz věty pro Presburgerovu aritmetiku od Philippa Rümmera

Languages

In other projects