Bevezetés az Intervallum-értékű paradigmába

Tartalom

1. Motivációk

Ebben a részben tehát megismerkedünk az intervallum-értékű logikával és egy olyan számításokat végző rendszerrel, amely a feletti intervallum-értékeket használja. Először néhány egyszerű érvet mutatunk arra, hogy miért lehet természetes, érdekes és hasznos az intervallumok használata.

A matematikai modellben az intervallum-értékeket pontokból és atomi intervallumokból építjük föl. A logikai operátorokat természetes módon terjesztjük ki az intervallum-értékekre. Megmutatjuk, hogy a népszerű többértékű logikai rendszerek hogyan modellezhetőek az intervallum-értékek segítségével.

A hagyományos számítógép bájtjait intervallum-értékekre cserélve kapjuk meg az intervallum-értékű számítógépet. A számítási teljességhez néhány, a már említett Boole-operátorokon kívüli operátort vezetünk be, pl. az eltolás és a szorzás operátorokat. Ezekkel az operátorokkal az intervallum-értékű számítógép már tudja szimulálni a hagyományos számításokat. Megmutatjuk, hogy elméleti értelemben az intervallum-értékű számítógép sokkal hatékonyabb, mint a klasszikus modell, az intervallum-értékek által megengedett (korlátlan, elvileg akár kontinuum) párhuzamosságnak köszönhetően. Megmutatjuk, hogy hogyan lehet a SAT és a qSAT problémát lineáris időben megoldani az intervallum-értékű számítógép segítségével, valamint hogyan tudunk olyan diszkrét értékű függvényeket kiszámolni, mint pl. a diszkrét logaritmus. A lista-reprezentáció segítségével hagyományos számítógépeken szimulálhatjuk az intervallum-értékű számításokat mind matematikai, mind hagyományos számítási értelemben. Természetesen ezzel a szimulációval elveszítjük a párhuzamosság okozta hatékonyságot.

A paradigma alapötlete, hogy az egységnyi területen tárolható információt nem tekintjük korlátosnak, szemben a Turing-gépek véges szalagábécéjével, vagy a Neumann-elvű gépek fix bithosszúságával. Ahogy látni fogjuk a számítás során megengedjük, hogy egyre több információt „tömörítsünk” egy intervallum-értékbe.

1. Motivációk

Amikor egy gyerek (vagy felnőtt) rajzol akkor tulajdonképpen pontokat, illetve szakaszokat vet a kétdimenziós papírra. Ha egy dimenzióra szorítkozunk, akkor pontokról és intervallumokról beszélhetünk. Így azt mondhatjuk az intervallum fogalma nagyon is kézenfekvő a mindennapi életben is.

Amint látni fogjuk pl. a DNS-számítások elméletében (III. RÉSZ), vagy a membrán-rendszereknél (IV. RÉSZ) előfordul hogy a természetben talált eszközök alapján készítünk matematikailag absztrakt számítási modelleket.

Vegyünk most is a „természetből” példát: a hagyományos fényképezés képfelbontása ismerten nagyon magas. A használt ezüst-oxid oldatok és vegyületek lehetővé teszik, hogy a fényképezőgép filmjén szinte atomonként változhasson az eredményezett kép. A fizikában és a kémiában több olyan mérési módszer is ismert, ahol a mérési hiba atomi méretekkel összemérhető. Például a modern LCD és TFT képernyőkön a polarizáció akár atomonként is változhat. Egy atom mérete, vagyis átmérője kb. ĺ (egy Ĺngstromnyi), ami métert jelent, ez azt jelenti, hogy egy 1 méter hosszú rúdon kb. atom helyezkedik el egymás mellett. Ha valamilyen fizikai mennyiséget atomonként tudunk változtatni és mérni, akkor ez egy olyan intervallumnak felel meg, ami pontból áll. Nem beszélve arról az esetről, ha nem egy sor, hanem több sor atomot tudunk úgy kezelni, mint egy rendezett listát.

A III. RÉSZ-ben a DNS számításokról lesz szó, az élő sejtekben nagyon hosszú DNS molekulák is előfordulnak: az ember genetikai kódja, ami minden sejtmagos sejtjében megtalálható, nagyságrendileg bázispárból áll.

Most is elrugaszkodunk kicsit a valóságtól és feltesszük, hogy végtelen (sőt kontinuum) sok pontból áll matematikai értelemben az intervallumunk. (Ahogy egy ceruzavonást is általában végtelen sok pontból állónak szoktunk feltételezni.)

Ebben a részben egy olyan új számítási paradigmát ismertetünk, amely a hagyományos kétértékű logika helyett egy végtelen értékű, az úgynevezett intervallum-értékű logikára épül. A következő fejezetben először ezt a logikát vizsgáljuk.