More about Recursive Structures: Descriptive Complexity and Zero-One Laws

: This paper continues our work on infinite, recursive structures. We investigate the descriptive complexity of several logics over recursive structures, including first-order, second-order, and fixpoint logic, exhibiting connections between expressibility of a property and its computational complexity. We then address 0--1 laws, proposing a version that applies to recursive structures, and using it to prove several non-expressibility results. 0 Introduction Infinite recursive structures, with recursive graphs as a special case, have been studied quite extensively in the past. Most interesting properties of recursive graphs have been shown to be undecidable, and many are actually outside the arithmetic hierarchy; see, e.g., [AMS, Be1, Be2, BG, H, HH1]. In [HH2] we considered recursive structures to be generalizations of finite relational data bases, and investigated the class of computable queries over them, the motivation being borrowed from [CH1]. A computable query is a (partial) r..