Intézeti szeminárium

Mindenki biztos benne, hogy tudja mit értsen kombinációs logika
alatt: logikai kapukból felépülő áramkör, melynek gráfja nem
tartalmaz kört. De valóban így van-e? Kényelmi, vagy egyéb
szempontok alapján gyakran behúzunk köröket előidéző éleket a
gráfba, mondván, hogy azok úgysem okoznak körbehivatkozást,
cirkuláris függőséget a jelek között. Vagyis a fogalom szemantikai,
nem pedig szintaktikai gyökerű. Kiderül azonban, hogy ez a
megfogalmazás cirkuláris függőségi alapon korántsem egyértelmű, és
a tisztázáshoz szükség van az aszinkron áramkörök működésének
mélyebb megértésére. Olyan modellre volna szükség, amely független
az áramkörben előforduló kapuk időzítésétől, az általuk előidézett
késleltetések mértékétől. Csakhogy jelenleg nincs ilyen modell, és
reálisan gondolkodva nem is lehet elképzelni olyan időzítés mentes
matematikai modellt, amely minden aszinkron áramkör esetén jól működik.
A kombinációs áramkörök azonban speciálisak, így van értelme megkérdezni,
hogy mely aszinkron áramkörök (gráfok) azok amelyek minden ésszerű
interpretáció mellett kombinációs logikát eredményeznek.

Az előadás a fenti kérdésekre próbál választ adni az aszinkron áramkörök
jelentésének axiomatikus definíciója által. A kiinduló észrevétel az,
hogy akármilyen természetű is legyen ez a kérdéses (időzítés mentes)
szemantika, az általa meghatározott struktúrának egy visszacsatolással
ellátott (traced) monoidális kategóriának kell lennie, mivel már a gráf
szintaxis is az. A feladat tehát egy adott algebrai elmélet (jelen
esetben a Boole függvények elmélete) által szabadon generált traced
monoidális kategórián belül azon morfizmusok megtalálása, amelyek
ekvivalensek az eredeti algebrai elmélet valamely morfizmusával.
Implicit módon ebbe az is beleértendő, hogy ez a szabad struktúra
valóban az eredeti elméletnek, nem pedig egy valódi kvóciensének a
kiterjesztése.