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

Visa fullständig post



Permalänk

http://urn.fi/URN:ISBN:978-952-10-5089-3
Titel: On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals
Författare: Bissell-Siders, Ryan
Medarbetare: Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, matematiska och statistiska institutionen
Utgivare: Helsingin yliopisto
Datum: 2008-11-21
Språk: en
Permanenta länken (URI): http://urn.fi/URN:ISBN:978-952-10-5089-3
http://hdl.handle.net/10138/21260
Nivå: Doktorsavhandling (sammanläggning)
Abstrakt: 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.
Subject: matematiikka
Licens: Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden.


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
onlinear.pdf 791.8Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post