# Problem 18: Finite Cursor Machines

1. A background structure ${\mathcal U}$ that consists of an infinite set $U$ of potential database entries, and some functions and predicates on $U$ (e.g., ${\mathcal U} = (\mathbb N, {\le}, +, \times)$)
2. A database schema $\sigma$ that consists of a finite number of relation symbols $R_1, \ldots, R_t$ of arities $r_1, \ldots, r_t$.
The input of a problem in this model is a database $D$ of schema $\sigma$ where $D$ is a collection of $t$ tables $R^D_1, \ldots, R^D_t$ and each table $R^D_i$ is a list of elements from $U^{r_i}$. On every input table, the FCM has a fixed number of cursors which can only move from top to bottom. Apart from this, the FCM also has an internal memory consisting of a constant number of “modes” (comparable to the states of a Turing machine) and a register for storing up to $o(n)$ many bits where $n$ is the total number of tuples in $D$.