On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://urn.fi/URN:ISBN:978-952-10-5089-3
Julkaisun nimi: On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals
Tekijä: Bissell-Siders, Ryan
Muu tekijä: Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, matematiikan ja tilastotieteen laitos
Julkaisija: Helsingin yliopisto
Päiväys: 2008-11-21
Kieli: en
URI: http://urn.fi/URN:ISBN:978-952-10-5089-3
http://hdl.handle.net/10138/21260
Opinnäytteen taso: Väitöskirja (artikkeli)
Tiivistelmä: We solve the Dynamic Ehrenfeucht-Fra\"iss\'e Game on linear orders for both players, yielding a normal form for quantifier-rank equivalence classes of linear orders in first-order logic, infinitary logic, and generalized-infinitary logics with linearly ordered clocks. We show that Scott Sentences can be manipulated quickly, classified into local information, and consistency can be decided effectively in the length of the Scott Sentence. We describe a finite set of linked automata moving continuously on a linear order. Running them on ordinals, we compute the ordinal truth predicate and compute truth in the constructible universe of set-theory. Among the corollaries are a study of semi-models as efficient database of both model-theoretic and formulaic information, and a new proof of the atomicity of the Boolean algebra of sentences consistent with the theory of linear order -- i.e., that the finitely axiomatized theories of linear order are dense.Lineaarijärjestysten kvanttoriastehierarkiassa olemme onnistunut laskemaan varsin tarkasti tiettyyn kvanttoriasteeseen asti ei-ekvilaenttien lineaarijärjesysten äärellisen lukumäärän. Ääretöaikaisten koneiden malleistä näimme että Turing-kone ja päättymät automaatteja pystyvät Gödelin konstruoituvan universumin laskemiseen.
Avainsanat: matematiikka
Tekijänoikeustiedot: Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
onlinear.pdf 791.8KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot