Logical Approaches to Computational Barriers

On Complexity of Ehrenfeucht Theories with Computable Model

Speaker:
| Alexander Gavryushkin |

Slot: |
Array, 14:50-15:10, col. 1 |

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 |