Punctual structures, automatic structures and index sets. Part 1

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. An interrelated notion is punctual structures where domain, functions, and relations belong to some fixed subrecursive class. In the first part we will give a sketch of the proof showing that the index set of punctually presentable computable structures is $\Sigma^1_1$ complete. In the second part we will show how to expand the idea for the $\Sigma^1_1$ completeness of the index set of automatically presentable computable structures. It follows from the last result that there is no natural way to tell whether a structure has, or does not have, an automatic presentation, answering the question of Khoussainov and Nerode.