Automata techniques for query inference machines (Q1849855)

Expressiveness of the languages \([+,<]\) of the first-order monadic predicate logic with addition, the relation ``less than'', and some additional fixed predicates, as well as the second-order monadic predicate language \([S,<]^2\) with some fixed additional predicates, both on the set of natural numbers, are considered, where \(S(x) = x+1\). The query language \(L\) is the set of formulas of the considered logic. A query over \(L\) is a formula \(F(X)\) of \(L\) with the unique free set variable \(X\). Every Turing machine \(M\) (the total variant of \(M\) is called inductive inference machine) is coded into a natural number \(e\), which is called a program (for \(M\)). A query inference machine is a total Turing machine that can ask queries in a particular query language about a computable set \(A\) to learn about \(A\) and magically gets the answers. Theorem. The set of computable sets cannot be learned by Turing machines with queries to the language \([+,<,\text{Pow}_a]\), where \(\text{Pow}_a\) is the predicate that tests if a number is a power of \(a\). The theorem is proved by transforming queries in \([+,<,\text{Pow}_a]\) into queries in \([S,<,\text{Pow}_a]^2\), which can be processed with the help of Büchi automata. Open question: Whether the first-order monadic predicate logic \([S,<,\text{Pow}_2,\text{Pow}_3]\) is quasi-cardinality decidable or not.