Graphs are not universal for online computability

作者：

Highlights：

•

摘要

We show that structures with only one binary function symbol are universal for “online” (punctual) computable structures. In contrast, we give a description of punctually categorical graphs which implies that graphs are not universal for online computability.

论文关键词：Computability,Logic,Abstract theory of online computation

论文评审过程：Received 6 December 2018, Revised 11 February 2020, Accepted 19 February 2020, Available online 13 March 2020, Version of Record 7 May 2020.

论文官网地址：https://doi.org/10.1016/j.jcss.2020.02.004