Graphs are not universal for online computability (Q2186809)

The authors study the so-called punctually universal classes of structures. Informally, a class of structures is called punctually universal if there is a uniform primitive recursive transformation that transforms any structure of finite signature into a structure in that class, and that this transformation has an inverse transformation, and both transformations also respect isomorphisms. They prove that the class of structures with only one binary function symbol is punctually universal. A description of punctually categorical graphs is given. It follows from this description that the class of graphs is not punctually universal.