Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
On Complexity of Ehrenfeucht Theories with Computable Model

Speaker: Alexander Gavryushkin
Slot: Tue, 14:50-15:10, Faraday A (col. 1)

Abstract

This work is devoted to investigation of complexity of theories 
with computable model and 
finite number of countable models up to isomorphism 
and also possibilities of location of computable model in the spectra
of Ehrefeucht theory. 

In the work for all m in omega there are  examples of Ehrefeucht 
theories of complexity 0^(m) with computable model. Also
there is example of theory with finite number of countable models which
all models are computable but not decidable. And example
of Ehrenfeucht theory which has uncomputable prime and saturated models
but one model of the theory has computable presentation. 


websites: Arnold Beckmann 2006-04-19 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net