Applications of Kolmogorov Complexity to Computable Model Theory
| dc.contributor.author | KHOUSSAINOV, Bakhadyr | en_US |
| dc.contributor.author | SEMUKHIN, Pavel | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.date.accessioned | 2006-09-07T06:46:20Z | en_US |
| dc.date.accessioned | 2017-01-23T06:59:57Z | |
| dc.date.available | 2006-09-07T06:46:20Z | en_US |
| dc.date.available | 2017-01-23T06:59:57Z | |
| dc.date.issued | 2006-09-07T06:46:20Z | en_US |
| dc.description.abstract | In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not countably categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of a uncountably categorical but not countably categorical saturated Sigma-0-1-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an uncountably categorical but not countably categorical theory whose only non-computable model is the prime one. | en_US |
| dc.format.extent | 463112 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2247 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRA9/06 | en_US |
| dc.title | Applications of Kolmogorov Complexity to Computable Model Theory | en_US |
| dc.type | Technical Report | en_US |