11institutetext: Ludwig-Maximilians-Universität München 11email:
<EMAIL_ADDRESS>22institutetext: Università di Verona 22email:
<EMAIL_ADDRESS>
# The Grothendieck computability model

Luis Gambarte 11 Iosif Petrakis 22

###### Abstract

Translating notions and results from category theory to the theory of
computability models of Longley and Normann, we introduce the Grothendieck
computability model and the first-projection-simulation. We prove some basic
properties of the Grothendieck computability model, and we show that the
category of computability models is a type-category, in the sense of Pitts. We
introduce the notion of a fibration and opfibration-simulation, and we show
that the first-projection-simulation is a split opfibration-simulation.

##  1 Introduction

The important role of category theory in computability theory has been
emphasised by Cockett and Hofstra in [1, 2, 3], who influenced the work of
Longley on computability models and simulations between them in [6, 7, 8]. The
categorical notion of equivalence between computability models that is studied
by Longley and Normann in [9] allowed a better way to “identify” seemingly
different computability structures. By associating to a computability model
$\mathbf{C}$ its category of assemblies
$\operatorname{\mathcal{A}\mathit{sm}}(\mathbf{C})$, Longley and Normann
established an equivalence of Morita-type between them. We can summarise the
work of Longley and Normann by the phrase “from computability models to
categories”.

In the previous work [10, 11, 12] of the second author the converse direction
i.e., “from categories to computability models”, is followed. Given a category
$\mathcal{C}$ and a presheaf $S$ on $\mathcal{C}$, the total computability
model $\operatorname{\mathbf{CM}}^{\mathrm{tot}}(\mathcal{C};S)$ was
introduced, and if $\mathcal{C}$ is a category with pullbacks and $S$
preserves pullbacks, the partial computability model
$\operatorname{\mathbf{CM}}^{\operatorname{prt}}(\mathcal{C};S)$ was studied.
In our joint work in progress [5] the notion of a computability model over a
category $\mathcal{C}$ with a base of computability, a notion close to
Rosolini’s concept of dominion in [15], and a pullback-preserving presheaf on
$\mathcal{C}$ is elaborated, generalising in this way both constructions, that
of $\operatorname{\mathbf{CM}}^{\mathrm{tot}}(\mathcal{C};S)$ and of
$\operatorname{\mathbf{CM}}^{\operatorname{prt}}(\mathcal{C};S)$. Strict
computability models are very close to categories of sets and partial
functions, but avoiding the equality rules for composition of partial
functions (as it is mentioned by Cockett in [1], p. 16, “program equality
itself is not well-understood”), they possess a more expressive power than
categories. Consequently, simulations, the arrows between computability
models, avoid equality too, involving certain forcing and tracking relations
instead.

Working within the direction “from categories to computability models” in this
paper too, we “translate” the categorical Grothendieck construction and the
categorical notion of split (op)fibration to the partial and without equality,
or relational framework of computability models. The Grothendieck
computability models become then the Sigma-objects, in the sense of Pitts
[14], in the category of computability models. We structure this paper as
follows:

  * •

In section 2 we include all basic definitions within the theory of
computability models necessary to the rest of this paper. Crucial to the
definition of the Grothendieck model is our introduction of the computability
model $\operatorname{\mathbf{Sets}}$, the computability model-counterpart to
the category of sets and functions (Definition 2). The introduced
representable-simulations correspond to the representable presheaves (Example
1).

  * •

In section 3 we define the Grothendieck computability model and the
corresponding first-projection-simulation (Proposition 1). We prove some basic
properties of the Grothendieck computability model, and we show that the
category of computability models $\operatorname{\mathsf{CompMod}}$ is a type-
category, in the sense of Pitts [14] (Theorem 3.1).

  * •

In section 4 we introduce the notion of a (split) fibration and opfibration-
simulation and we show that the first-projection-simulation
$\mathbf{\operatorname{\mathsf{pr}}_{1}}\colon\sum_{\mathbf{C}}\boldsymbol{\gamma}\operatorname{\rightarrowtriangle}\mathbf{C}$
is a (split) opfibration-simulation (Proposition 3 and Corollary 1).

  * •

In section 5 we include some questions and topics for future work.

For all notions and results from category theory that are used here without
explanation or proof we refer to [17]. For various examples of computability
models and simulations from higher-order computability theory we refer to [9].

##  2 Basic definitions

###### Definition 1

A $($strict$)$ computability model $\mathbf{C}$ consists of the following
data: a class $T$, whose members are called type names; for each $t\in T$ a
set $\mathbf{C}(t)$ of data types; for each $s,t\in T$ a class
$\mathbf{C}[s,t]$ of computable functions, i.e., partial functions from
$\mathbf{C}(s)$ to $\mathbf{C}(t)$. Moreover, for every $r,s,t\in T$ the
following hold:

  1. 1.

The identity $\mathbf{1}_{\mathbf{C}(t)}$ is in $\mathbf{C}[t,t]$.

  2. 2.

For every $f\in\mathbf{C}[r,s]$ and $g\in\mathbf{C}[s,t]$ we have that $g\circ
f\in\mathbf{C}[r,t]$.

Next, we describe the computability model of sets and partial functions
$\operatorname{\mathbf{Sets}}$, as the computability model-analogue to the
category of sets and functions $\operatorname{\mathsf{Sets}}$.

###### Definition 2

The computability model $\operatorname{\mathbf{Sets}}$ has as type names the
class of sets and as data types the set $U$ itself, for every type name $U$.
If $U,V$ are sets, the computable functions from $U$ to $V$ is the class of
partial functions from $U$ to $V$.

A partial arrow $(i,f)\colon a\rightharpoonup b$ in a category $\mathcal{C}$
consists of a monomorphism $i\colon\operatorname{dom}(i)\to a$ and an arrow
$f\colon\operatorname{dom}(i)\to b$ in $\mathcal{C}$. Given a (covariant)
presheaf $S\colon\mathcal{C}\to\operatorname{\mathsf{Sets}}$, we write
$S(i,f)$ instead of $\big{(}S(i),S(f)\big{)}$. In [12] computability models
over categories and presheaves on them were defined in a canonical way.

###### Definition 3

Let $\mathcal{C}$ be a category and
$S\colon\mathcal{C}\to\operatorname{\mathsf{Sets}}$ a presheaf on
$\mathcal{C}$. The total canonical computability model
$\operatorname{\mathbf{CM}}^{\operatorname{tot}}(\mathcal{C};S)$ over
$\mathcal{C}$ and $S$ has as type names the class of objects $\mathcal{C}_{0}$
of $\mathcal{C}$ and data types the sets $S(c)$, for every
$c\in\mathcal{C}_{0}$. If $c_{1},c_{2}\in\mathcal{C}_{0}$, the (total)
functions from $S(c_{1})$ to $S(c_{2})$ is the class
$\\{S(f)\leavevmode\nobreak\ |\leavevmode\nobreak\
f\in\operatorname{Hom}(c_{1},c_{2})\\}$. The partial canonical computability
model $\operatorname{\mathbf{CM}}^{\operatorname{prt}}(\mathcal{C};S)$ over
$\mathcal{C}$ and a pullback-preserving presheaf $S$ has the same type names
and data types, while the partial functions from $S(c_{1})$ to $S(c_{2})$ is
the class $\\{S(i,f)\leavevmode\nobreak\ |\leavevmode\nobreak\ (i,f)\colon
c_{1}\rightharpoonup c_{2}\\}$.

The pullback-preserving property on $S$ is necessary to prove that
$\operatorname{\mathbf{CM}}^{\operatorname{prt}}(\mathcal{C};S)$ is a
computability model. We can also use the category
$\operatorname{\mathsf{Sets}}^{\operatorname{prt}}$ of sets and partial
functions, and the computability model
$\operatorname{\mathbf{CM}}^{\operatorname{tot}}(\operatorname{\mathsf{Sets}}^{\operatorname{prt}},\operatorname{id}_{\operatorname{\mathsf{Sets}}^{\operatorname{prt}}})$
is the computability model $\operatorname{\mathbf{Sets}}$ of Definition 2.
Next, we describe the arrows in the category of computability models
$\operatorname{\mathsf{CompMod}}$. A notion of contravariant simulation can
also be defined, allowing the contravariant version of the Grothendieck
construction for computability models.

###### Definition 4

A simulation $\boldsymbol{\gamma}$ from $\mathbf{C}$ $($over $T)$ to
$\mathbf{D}$ $($over $U)$ consists of a class-function $\gamma\colon T\to U$
and a relation
$\Vdash_{t}^{\gamma}\subseteq\mathbf{D}\big{(}\gamma(t)\big{)}\times\mathbf{C}(t)$
$($a so-called forcing relation$)$, for each $t\in T$, subject to the
following conditions:

  1. 1.

For each $x\in\mathbf{C}(t)$ there exists some $y\in\mathbf{D}(\gamma(t))$,
such that $y\Vdash_{t}^{\gamma}x$.

  2. 2.

For each $f\in\mathbf{C}[s,t]$ there exists some
$f^{\prime}\in\mathbf{D}\big{[}\gamma(s),\gamma(t)\big{]}$ such that

$\forall_{x\in\mathbf{C}(s)}\forall_{y\in\mathbf{D}(\gamma(s))}\big{(}x\in\operatorname{dom}(f)\wedge
y\Vdash_{s}^{\gamma}x\Rightarrow y\in\operatorname{dom}(f^{\prime})\wedge
f^{\prime}(y)\Vdash_{t}^{\gamma}f(x)\big{)}.$

In this case we say that $f^{\prime}$ tracks $f$, and we write
$f^{\prime}\Vdash_{(s,t)}^{\gamma}f$. We also write
$\boldsymbol{\gamma}\colon\mathbf{C\operatorname{\rightarrowtriangle}D}$ for a
simulation $\boldsymbol{\gamma}$ from $\mathbf{C}$ to $\mathbf{D}$. We call a
simulation
$\boldsymbol{\gamma}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$
a $($covariant$)$ presheaf-simulation. The identity simulation
$\mathbf{1}_{\mathbf{C}}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\mathbf{C}$
is the pair
$\big{(}\operatorname{id}_{T},(\Vdash^{\mathbf{\iota}_{\mathbf{C}}}_{t})_{t\in
T}\big{)}$, where
$x{{}^{\prime}}\Vdash^{\mathbf{\iota}_{\mathbf{C}}}_{t}x:\Leftrightarrow
x{{}^{\prime}}=x$, for every $x{{}^{\prime}},x\in\mathbf{C}(t)$. If
$\boldsymbol{\delta}\colon\mathbf{D}\operatorname{\rightarrowtriangle}\mathbf{E}$,
the composite simulation
$\boldsymbol{\delta}\circ\boldsymbol{\gamma}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\mathbf{E}$
is the pair
$\big{(}\delta\circ\gamma,(\Vdash^{\mathbf{\delta}\circ\mathbf{\gamma}}_{t})_{t\in
T}\big{)}$, where the relation
$\Vdash^{\mathbf{\delta}\circ\mathbf{\gamma}}_{t}\subseteq\mathbf{E}\big{(}\delta(\gamma(t))\big{)}\times\mathbf{C}(t)$
is defined by

$z\Vdash^{\mathbf{\delta}\circ\mathbf{\gamma}}_{t}x:\Leftrightarrow\exists_{y\in\mathbf{D}(\gamma(t))}\big{(}z\Vdash^{\mathbf{\delta}}_{\gamma(t)}y\
\wedge\ y\Vdash^{\mathbf{\gamma}}_{t}x\big{)}.$

The following presheaf-simulations on a computability model $\mathbf{C}$
correspond to the representable functors $\operatorname{Hom}(a,-)$ over $a$ in
a category $\mathcal{C}$.

###### Example 1

Let $\mathbf{C}$ be a locally-small computability model over $T$, i.e., the
class $\mathbf{C}[s,t]$ of computable functions from $\mathbf{C}(s)$ to
$\mathbf{C}(t)$ is a set, for every $s,t\in T$. If $t_{0}\in T$, the
representable-simulation
$\boldsymbol{\gamma}_{t_{0}}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$
consists of the class-function $\gamma_{t_{0}}\colon
T\to\operatorname{\mathsf{Sets}}$, defined by
$\gamma_{t_{0}}(t):=\mathbf{C}[t_{0},t]$, for every $t\in T$, and the forcing
relations
$\Vdash_{t}^{\gamma_{t_{0}}}\subseteq\mathbf{C}[t_{0},t]\times\mathbf{C}(t)$,
defined by

$f\Vdash_{t}^{\gamma_{t_{0}}}x:\Leftrightarrow\exists_{y\in\operatorname{dom}(f)}\big{(}f(y)=x\big{)}.$

To show that $\boldsymbol{\gamma}_{t_{0}}$ is a simulation, we also need to
suppose that $\mathbf{C}$ is left-regular i.e., $\forall_{t\in
T}\forall_{x\in\mathbf{C}(t)}\exists_{f\in\mathbf{C}[t_{0},t]}\exists_{y\in\operatorname{dom}(f)}\big{(}f(y)=x\big{)}$.
All computability models that include the constant functions are left-regular
(such as Kleene’s first model $K_{1}$ over $T=\\{0\\}$ with
$\mathbf{C}(0)=\mathbb{N}$, and $\mathbf{C}[0,0]$ the Turing-computable
partial functions from $\mathbb{N}$ to $\mathbb{N}$). If
$f\in\mathbf{C}[s,t]$, it is easy to show that
$f^{*}\Vdash_{(s,t)}^{\gamma_{t_{0}}}f$, where $f^{*}$ is the total function
from $\mathbf{C}[t_{0},s]$ to $\mathbf{C}[t_{0},t]$, defined by
$f^{*}(g):=f\circ g$, for every $g\in\mathbf{C}[t_{0},s]$. A right-regularity
condition on a locally-small computability model is needed, to define the
contravariant representable-simulations
$\mathbf{\delta}_{t_{0}}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$,
where ${\delta}_{t_{0}}\colon\mathbf{C}\to\operatorname{\mathsf{Sets}}$ is
defined by $\delta_{t_{0}}(t):=\mathbf{C}[t,t_{0}]$, for every $t\in T$.

##  3 The Grothendieck computability model

The Grothendieck computability model is the categorical counterpart to the
category of elements, a special case of the general categorical Grothendieck
construction. A category $\mathcal{C}$ is replaced by a computability model
$\mathbf{C}$, and a (covariant) presheaf
$S\colon\mathcal{C}\to\operatorname{\mathsf{Sets}}$ by a (covariant)
simulation
$\boldsymbol{\gamma}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$.
Moreover, the first-projection functor is replaced by the first-projection-
simulation.

###### Proposition 1

Let $\mathbf{C}$ be a computability model over the class $T$ together with a
simulation
$\boldsymbol{\gamma}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$.
The structure $\sum_{\mathbf{C}}\boldsymbol{\gamma}$ with type names the class

$\sum_{t\in T}\boldsymbol{\gamma}(t):=\big{\\{}(t,b)\leavevmode\nobreak\
|\leavevmode\nobreak\ t\in T\hbox{ and }b\in\gamma(t)\big{\\}},$

with data types, for every $(t,b)\in\sum_{t\in T}\boldsymbol{\gamma}(t)$, the
sets

$\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t,b):=\big{\\{}y\in\mathbf{C}(t)\leavevmode\nobreak\
|\leavevmode\nobreak\ b\Vdash_{t}^{\gamma}y\big{\\}},$

and computable functions from
$\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(s,a)$ to
$\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t,b)$ the classes

$\Big{\\{}f\in\mathbf{C}[s,t]\leavevmode\nobreak\ |\leavevmode\nobreak\
\forall_{x\in\operatorname{dom}(f)}\Big{(}x\in\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(s,a)\Rightarrow
f(x)\in\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t,b)\Big{)}\Big{\\}},$

is a computability model. The class-function
$\operatorname{\mathsf{pr}}_{1}\colon\sum_{t\in T}\boldsymbol{\gamma}(t)\to
T$, defined by the rule $(t,b)\mapsto t$, and the forcing relations, defined,
for every $(t,b)\in\sum_{t\in T}\boldsymbol{\gamma}(t)$, by

$y{{}^{\prime}}\Vdash_{(t,b)}^{\operatorname{\mathsf{pr}}_{1}}y:\Leftrightarrow
y{{}^{\prime}}=y,$

determine the first-projection-simulation
$\operatorname{\mathbf{pr}}_{1}\colon\sum_{\mathbf{C}}\boldsymbol{\gamma}\operatorname{\rightarrowtriangle}\mathbf{C}$.

###### Proof

We show that the computable functions include the identities and are closed
under composition. Notice that the defining property of the computable
functions in the Grothendieck model is equivalent to the condition
$a\Vdash_{s}^{\gamma}x\Rightarrow b\Vdash_{t}^{\gamma}f(x)$, for every
$x\in\operatorname{dom}(f)$. If $(t,b)\in\sum_{t\in T}\boldsymbol{\gamma}(t)$,
then the identity on $\sum_{\mathbf{C}}\boldsymbol{\gamma}(t,b)$ is the
identity on $\mathbf{C}(t)$, i.e., $\mathbf{1}_{\mathbf{C}(t)}$ is a
computable function from
$\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t,b)$ to itself: if
$x\in\mathbf{C}(t)$, then the implication $b\Vdash_{t}^{\gamma}x\Rightarrow
b\Vdash_{t}^{\gamma}x$ holds trivially. If $g$ is a computable function from
$\sum_{\mathbf{C}}\boldsymbol{\gamma}(t,b)$ to
$\sum_{\mathbf{C}}\boldsymbol{\gamma}(u,c)$ and $f$ is a computable function
from $\sum_{\mathbf{C}}\boldsymbol{\gamma}(s,a)$ to
$\sum_{\mathbf{C}}\boldsymbol{\gamma}(t,b)$, then $g\circ f$ is a computable
function from $\sum_{\mathbf{C}}\boldsymbol{\gamma}(s,a)$ to
$\sum_{\mathbf{C}}\boldsymbol{\gamma}(u,c)$. For that, let
$x\in\operatorname{dom}(f)$ and $f(x)\in\operatorname{dom}(g)$. If
$a\Vdash_{s}^{\gamma}x$, then $b\Vdash_{t}^{\gamma}f(x)$, and hence
$c\Vdash_{u}^{\gamma}g(f(x))$. Next, we show that
$\operatorname{\mathbf{pr}}_{1}$ is a simulation. If
$y\in\sum_{\mathbf{C}}\boldsymbol{\gamma}(t,b)$, then
$x\Vdash_{(t,b)}^{\operatorname{\mathsf{pr}}_{1}}x$, and if $f$ is a
computable function from $\sum_{\mathbf{C}}\boldsymbol{\gamma}(s,a)$ to
$\sum_{\mathbf{C}}\boldsymbol{\gamma}(t,b)$, then
$f\Vdash_{((s,a),(t,b))}^{\operatorname{\mathsf{pr}}_{1}}f$.

The following fact is straightforward to prove.

###### Proposition 2

Let $\mathcal{C}$ be a category and
$S\colon\mathcal{C}\to\operatorname{\mathsf{Sets}}$ a pullback-preserving
presheaf on $\mathcal{C}$. Let
$\gamma^{S}\colon\mathcal{C}_{0}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$
be defined via $\gamma^{S}(c)=S(c)$ and the relations
$\Vdash_{c}^{\gamma^{S}}$ are simply the diagonal, and let
$\\{\operatorname{\mathsf{pr}}_{2}\\}\colon\sum_{\mathcal{C}}S\to\operatorname{\mathsf{Sets}}$
be defined by $\\{\operatorname{\mathsf{pr}}_{2}\\}(c,x):=\\{x\\}$ and if
$f\colon(c,x)\to(d,y)$ in $\sum_{\mathcal{C}}S$, let $[S(f)](x):=y$. Then

$\sum_{\operatorname{\mathbf{CM}}^{\operatorname{prt}}(\mathcal{C};S)}\boldsymbol{\gamma}^{S}=\operatorname{\mathbf{CM}}^{\operatorname{prt}}\Big{(}\sum_{\mathcal{C}}S;\\{\operatorname{\mathsf{pr}}_{2}\\}\Big{)}.$

###### Remark 1

The functor
$\mathbf{C}\mapsto\operatorname{\mathcal{A}\mathit{sm}}(\mathbf{C})$ studied
in [9] does not “preserve” the Grothendieck construction. Namely, if
$\mathbf{1}$ is a terminal computability model with type names
$\\{\emptyset\\}$, data type $\mathbf{1}(\emptyset)=\\{\emptyset\\}$, and as
only computable function the identity, then one can define a presheaf
$\operatorname{id}_{\mathbf{1}}\colon\mathbf{1}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$,
and show that

$\operatorname{\mathcal{A}\mathit{sm}}\bigg{(}\sum_{\mathbf{1}}\operatorname{id}_{\mathbf{1}}\bigg{)}\neq\sum_{\operatorname{\mathcal{A}\mathit{sm}}{(\mathbf{1})}}\operatorname{\mathcal{A}\mathit{sm}}(\operatorname{id}_{\mathbf{1}}).$

Next we show that the category of computability models
$\operatorname{\mathsf{CompMod}}$ is a type-category, in the sense of Pitts
[14], pp. 110-111, a reformulation of Cartmell’s categories with attributes in
[4]. These categories are what we call $(\mathrm{fam},\Sigma)$-categories with
a terminal object in [13], and serve as categorical models of dependent type
systems. First, we lift a simulation
$\boldsymbol{\gamma}\colon\mathbf{C\operatorname{\rightarrowtriangle}D}$ to a
simulation between the Grothendieck computability models
$\sum_{\mathbf{C}}(\boldsymbol{\delta}\circ\boldsymbol{\gamma})$ and
$\sum_{\mathbf{D}}\boldsymbol{\delta}$.

###### Lemma 1

Let $\mathbf{C,D}$ be computability models over the classes $T,U$
respectively, and
$\boldsymbol{\gamma}\colon\mathbf{C\operatorname{\rightarrowtriangle}D},\boldsymbol{\delta}\colon\mathbf{D}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$
simulations. There is a simulation
$\sum_{\boldsymbol{\delta}}\boldsymbol{\gamma}\colon\sum_{\mathbf{C}}(\boldsymbol{\delta}\circ\boldsymbol{\gamma})\operatorname{\rightarrowtriangle}\sum_{\mathbf{D}}\boldsymbol{\delta}$,
such that the following is a pullback square

${\sum_{\mathbf{C}}(\boldsymbol{\delta}\circ\boldsymbol{\gamma})}$${\sum_{\mathbf{D}}\boldsymbol{\delta}}$${\mathbf{C}}$${\mathbf{D}.}$$\rightarrowtriangle$$\scriptstyle{\sum_{\boldsymbol{\delta}}\boldsymbol{\gamma}}$$\rightarrowtriangle$$\scriptstyle{\operatorname{\mathbf{pr}}_{1}}$$\rightarrowtriangle$$\scriptstyle{\operatorname{\mathbf{pr}}_{1}}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\gamma}}$

###### Proof

To define $\sum_{\boldsymbol{\delta}}\boldsymbol{\gamma}$, let the underlying
class-function $\sum_{{\delta}}{\gamma}\colon\sum_{t\in
T}\boldsymbol{\gamma}(t)\to\sum_{u\in U}\boldsymbol{\delta}(u)$ be defined by
the rule $(t,b)\mapsto\big{(}\gamma(t),b)$. The corresponding forcing
relations are defined by
$x^{\prime}\Vdash_{(t,b)}^{\sum_{{\delta}}{\gamma}}x:\Leftrightarrow
x^{\prime}\Vdash_{t}^{\gamma}x.$ It is straightforward to show that
$\sum_{\boldsymbol{\delta}}\boldsymbol{\gamma}$ is a simulation. Next we show
that the above square commutes. On the underlying classes this is immediate as

$\operatorname{\mathsf{pr}}_{1}\big{(}\sum_{{\delta}}{\gamma}(t,b)\big{)}=\operatorname{\mathsf{pr}}_{1}\big{(}\gamma(t)\big{)}=\gamma\big{(}\operatorname{\mathsf{pr}}_{1}(t,b)\big{)}.$

On the forcing relations we observe that if
$x^{\prime}\Vdash_{(t,b)}^{\operatorname{\mathsf{pr}}_{1}\circ\sum_{{\delta}}{\gamma}}x$,
then $x^{\prime}\Vdash_{(t,b)}^{\sum_{{\delta}}{\gamma}}x$, and thus
$x^{\prime}\Vdash_{t}^{\gamma}x$, which is also equivalent to
$x^{\prime}\Vdash_{(t,b)}^{\gamma\circ\operatorname{\mathsf{pr}}_{1}}x$.
Finally, we show the pullback property. Let a computability model $\mathbf{E}$
over a class $V$ with simulations $\boldsymbol{\alpha},\boldsymbol{\beta}$ be
given, such that the following rectangle commutes

${\mathbf{E}}$${\sum_{\mathbf{D}}\boldsymbol{\delta}}$${\mathbf{C}}$${\mathbf{D}.}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\beta}}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\alpha}}$$\rightarrowtriangle$$\scriptstyle{\operatorname{\mathbf{pr}}_{1}}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\gamma}}$
(1)

We find a unique simulation
$\boldsymbol{\zeta}\colon\mathbf{E}\operatorname{\rightarrowtriangle}\sum_{\mathbf{C}}(\boldsymbol{\delta}\circ\boldsymbol{\gamma})$
such that both following triangles

${\mathbf{E}}$${\sum_{\mathbf{C}}(\boldsymbol{\delta}\circ\boldsymbol{\gamma})}$${\sum_{\mathbf{D}}\boldsymbol{\delta}}$${\mathbf{C}}$${\mathbf{D}}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\zeta}}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\alpha}}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\beta}}$$\rightarrowtriangle$$\scriptstyle{\sum_{\boldsymbol{\delta}}\boldsymbol{\gamma}}$$\rightarrowtriangle$$\scriptstyle{\operatorname{\mathbf{pr}}_{1}}$$\rightarrowtriangle$$\scriptstyle{\operatorname{\mathbf{pr}}_{1}}$$\rightarrowtriangle$$\scriptstyle{\boldsymbol{\gamma}}$

commute. First we define $\zeta$ on the level of the underlying classes. If
$v\in V$, let $\zeta(v)=\big{(}\alpha(v),c\big{)}$, where
$c\in\delta(\gamma(v))$ is the unique $c$ such that $\beta(v)=(u,c)$ for some
$u$. Clearly, $\zeta$ is well-defined. Next we define the forcing relations.
Let

$x^{\prime}\Vdash_{v}^{\zeta}x:\Leftrightarrow
x^{\prime}\Vdash_{v}^{\alpha}x.$

This relations are well-defined and in conjunction with the aforementioned
class-function they constitute a simulation. Observe that the two triangles
already commute on the level of the underlying class-functions, so it remains
to check the forcing relations. Assume we are given $v\in V$ and
$x^{\prime\prime}\in\mathbf{E}(v),x^{\prime}\in\Big{(}\sum_{\mathbf{D}}\boldsymbol{\delta}\Big{)}\big{(}\beta(v)\big{)}$
and $x\in\mathbf{C}\big{(}\alpha(v)\big{)}$ such that

$x^{\prime}\Vdash_{v}^{\beta}x^{\prime\prime}\hbox{ and
}x\Vdash_{v}^{\alpha}x^{\prime\prime}.$

By definition we have to show that there exist $y_{1},y_{2}$ such that

$x^{\prime}\Vdash_{\zeta(v)}^{\sum_{{\delta}}{\gamma}}y_{1}\hbox{ and
}y_{1}\Vdash_{v}^{\zeta}x^{\prime\prime},\hbox{ and
}x\Vdash_{\zeta(v)}^{\operatorname{\mathsf{pr}}_{1}}y_{2}\hbox{ and
}y_{2}\Vdash_{v}^{\zeta}x^{\prime\prime}.$

We know that the square (1) commutes and
$x^{\prime}\Vdash_{(\sum_{{\delta}}{\gamma})(\zeta(v))}^{\operatorname{\mathsf{pr}}_{1}}x^{\prime}$,
thus from $x^{\prime}\Vdash_{v}^{\beta}x^{\prime\prime}$ we conclude that
$x^{\prime}\Vdash_{v}^{\gamma\circ\alpha}x^{\prime\prime}$. This in turn
ensures that there is $y$ such that $x^{\prime}\Vdash_{\alpha(v)}^{\gamma}y$
and $y\Vdash_{v}^{\alpha}x^{\prime\prime}$. By definition of
$\sum_{{\delta}}{\gamma}$ we then have that
$x^{\prime}\Vdash_{\alpha(v)}^{\sum_{{\delta}}{\gamma}}y$ and thus $y$ is our
desired $y_{1}$. For $y_{2}$ we simply choose $x$ and it is easy to see that
this fulfills the requirements. The above implications also work in the
reverse direction. It is immediate to show that $\boldsymbol{\zeta}$ is the
unique simulation making the triangles commutative, as it is determined by the
definition of $\boldsymbol{\beta},\boldsymbol{\alpha}$.

###### Lemma 2

If $\mathbf{C,D,E}\in\operatorname{\mathsf{CompMod}}$,
$\boldsymbol{\gamma}\colon\mathbf{C\operatorname{\rightarrowtriangle}D},\boldsymbol{\delta}\colon\mathbf{D\operatorname{\rightarrowtriangle}E}$,
and
$\boldsymbol{\epsilon}\colon\mathbf{E}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$
is a presheaf-simulation, then the following strictness conditions hold:
(i)
$\sum_{\boldsymbol{\epsilon}}\mathbf{1}_{\mathbf{E}}=\mathbf{1}_{\sum_{\mathbf{E}}\boldsymbol{\epsilon}}$.
(ii)
$\sum_{\boldsymbol{\epsilon}}(\boldsymbol{\delta}\circ\boldsymbol{\gamma})=\sum_{\boldsymbol{\epsilon}}\boldsymbol{\delta}\circ\sum_{(\boldsymbol{\epsilon}\circ\boldsymbol{\delta})}\boldsymbol{\gamma}$.

###### Proof

(i) It suffices to observe that by its definition the simulation
$\sum_{\boldsymbol{\epsilon}}\mathbf{1}_{\mathbf{E}}$ on the level of the
underlying class takes a pair $(t,u)$ to
$(\mathbf{1}_{\mathbf{E}}(t),u)=(t,u)$, so on the level of the underlying
class-functions the two simulations agree. For the forcing relations we see
that both simulations are the corresponding diagonal.
(ii) To verify this equation on the level of underlying classes we have that

$\sum_{\boldsymbol{\epsilon}}(\boldsymbol{\delta}\circ\boldsymbol{\gamma})(t,b)=\big{(}t,(\delta\circ\gamma)(b)\big{)}=\sum_{\boldsymbol{\epsilon}}\boldsymbol{\delta}\big{(}t,\gamma(b)\big{)}=\sum_{\boldsymbol{\epsilon}}\boldsymbol{\delta}\Big{(}\Big{(}\sum_{\boldsymbol{\epsilon}\circ\boldsymbol{\delta}}\boldsymbol{\gamma}\Big{)}(t,b)\Big{)}.$

For the forcing relations we simply remark that
$x\Vdash_{(t,b)}^{\sum_{\epsilon}{\delta\circ\gamma}}y$ if and only if
$x\Vdash_{t}^{\delta\circ\gamma}y$. Similarly, we have that
$x\Vdash_{(t,b)}^{\sum_{\epsilon}{\delta}}y$ if and only if
$x\Vdash_{t}^{\delta}y$, and
$x\Vdash_{(t,b)}^{\sum_{\epsilon\circ\delta}{\gamma}}y$ if and only if
$x\Vdash_{t}^{\gamma}y$. Hence,
$x\Vdash_{(t,b)}^{\sum_{\epsilon}{\delta}\circ\sum_{\epsilon\circ\delta}\gamma}y$
if and only if $x\Vdash_{t}^{\delta\circ\gamma}z$, which by the above is
equivalent to $x\Vdash_{(t,b)}^{\sum_{\epsilon}{\delta\circ\gamma}}z$.

###### Theorem 3.1

The category $\operatorname{\mathsf{CompMod}}$ is a type-category.

###### Proof

This follows immediately from Lemma 1, Lemma 2, and the fact that
$\operatorname{\mathsf{CompMod}}$ has a terminal object, as explained in
Remark 1.

##  4 Fibration-simulations and opfibration-simulations

The (covariant) Grothendieck construction allows the generation of fibrations
(opfibrations), as the first-projection functor
$\operatorname{\mathsf{pr}}_{1}\colon\sum_{\mathcal{C}}P\to\mathcal{C}$ is a
(split) opfibration, if $P$ is a covariant presheaf, or a (split) fibration,
if $P$ is a contravariant presheaf. In this section we introduce the notion of
a fibration and opfibration-simulation and we show that the first-projection-
simulation
$\mathbf{\operatorname{\mathsf{pr}}_{1}}\colon\sum_{\mathbf{C}}\boldsymbol{\gamma}\operatorname{\rightarrowtriangle}\mathbf{C}$
is a (split) opfibration-simulation, as we work with covariant presheaf-
simulations. The dual result is shown similarly.

In this section, $\mathbf{E}$ is a computability model over $T$ and
$\mathbf{B}$ a computability model over $U$. Moreover, the pair

$\boldsymbol{\varpi}:=\bigg{(}\varpi\colon\colon T\to U,\
\big{(}\Vdash^{\varpi}_{t}\big{)}_{t\in T}\bigg{)}$

is a simulation of type
$\mathbf{E}\operatorname{\rightarrowtriangle}\mathbf{B}$. In contrast to what
it holds for functors, for simulations
$\boldsymbol{\gamma}\colon\mathbf{E\rightarrowtriangle B}$ each computable
function $f$ in $\mathbf{E}$ is tracked, in general, by a multitude of maps
$f^{\prime}$ in $\mathbf{B}$. Thus, for each opspan

${\mathbf{E}(t_{1})}$${\mathbf{E}(t_{2})}$${\mathbf{E}(t_{3})}$$\rightarrowtriangle$$\scriptstyle{f}$$\rightarrowtriangle$$\scriptstyle{g}$

we have a whole class, in general, of opspans

${\mathbf{B}(\gamma(t_{1}))}$${\mathbf{B}(\gamma(t_{2}))}$${\mathbf{B}(\gamma(t_{3}))}$$\rightarrowtriangle$$\scriptstyle{f^{\prime}}$$\rightarrowtriangle$$\scriptstyle{g^{\prime}}$

such that $f^{\prime}$ tracks $f$ and $g^{\prime}$ tracks $g$.

######  Definition 5 (Cartesian computable function)

Let $f^{\prime}\in\mathbf{B}[s,s^{\prime}]$ and $t^{\prime}\in T$, such that
$\varpi(t^{\prime})=s^{\prime}$ be given. We call a computable function
$f\in\mathbf{E}[t,t^{\prime}]$ cartesian for $f^{\prime}$ and $t^{\prime}$, if
$f^{\prime}\Vdash_{(t,t^{\prime})}^{\varpi}f$, and given computable functions
$g\in\mathbf{E}[t^{\prime\prime},t^{\prime}],g^{\prime}\in\mathbf{B}[\varpi(t^{\prime\prime}),\varpi(t^{\prime})]$,
and $h\in\mathbf{B}[\varpi(t^{\prime\prime}),\varpi(t)]$ as in the following
diagram

${\mathbf{E}(t)}$${\mathbf{B}(\varpi(t))}$${\mathbf{E}(t^{\prime\prime})}$${\mathbf{B}(\varpi(t^{\prime\prime}))}$${\mathbf{E}(t^{\prime})}$${\mathbf{B}(\varpi(t^{\prime}))}$$\scriptstyle{\Vdash_{t}^{\varpi}}$$\scriptstyle{f^{\prime}}$$\scriptstyle{k}$$\scriptstyle{\Vdash_{t^{\prime\prime}}^{\varpi}}$$\scriptstyle{g}$$\scriptstyle{g^{\prime}}$$\scriptstyle{h}$$\scriptstyle{\Vdash_{t^{\prime}}^{\varpi}}$$\scriptstyle{f}$

that is $g^{\prime}$ tracks $g$, there is some
$k\in\mathbf{E}[t^{\prime\prime},t]$ satisfying the following property:
$h\Vdash_{(t^{\prime\prime},t)}^{\varpi}k$, and for every
$x\in\mathbf{E}(t^{\prime\prime}),y\in\mathbf{B}(\varpi(t^{\prime\prime}))$,
such that $y\Vdash_{t^{\prime\prime}}^{\varpi}x$,
$y\in\operatorname{dom}(f^{\prime}\circ h)\cap\operatorname{dom}(g^{\prime}),$
and $f^{\prime}(h(y))=g^{\prime}(y)$, then $x\in\operatorname{dom}(f\circ
k)\cap\operatorname{dom}(g)$ and $g(x)=f(k(x))$.

######  Definition 6 (Opcartesian computable function)

Let $f^{\prime}\in\mathbf{B}[s^{\prime},s]$ and $t^{\prime}\in T$, such that
$\varpi(t^{\prime})=s^{\prime}$ be given We call a computable function
$f\in\mathbf{E}[t^{\prime},t]$ opcartesian for $f^{\prime}$ and $t^{\prime}$,
if $f^{\prime}\Vdash_{(t^{\prime},t^{\prime})}^{\varpi}f$, and given
computable functions
$g\in\mathbf{E}[t^{\prime},t^{\prime\prime}],g^{\prime}\in\mathbf{B}[\varpi(t^{\prime}),\varpi(t^{\prime\prime})]$
and $h\in\mathbf{B}[\varpi(t),\varpi(t^{\prime\prime})]$ as in the following
diagram

${\mathbf{E}(t)}$${\mathbf{B}(\varpi(t))}$${\mathbf{E}(t^{\prime\prime})}$${\mathbf{B}(\varpi(t^{\prime\prime}))}$${\mathbf{E}(t^{\prime})}$${\mathbf{B}(\varpi(t^{\prime}))}$$\scriptstyle{l}$$\scriptstyle{f}$$\scriptstyle{\Vdash_{t}^{\varpi}}$$\scriptstyle{f^{\prime}}$$\scriptstyle{\Vdash_{t^{\prime\prime}}^{\varpi}}$$\scriptstyle{g}$$\scriptstyle{g^{\prime}}$$\scriptstyle{h}$$\scriptstyle{\Vdash_{t^{\prime}}^{\varpi}}$

that is $g^{\prime}$ tracks $g$, there is some
$l\in\mathbf{E}[t,t^{\prime\prime}]$ satisfying the following property: $h$
tracks $l$, and for every
$x\in\mathbf{E}(t^{\prime}),y\in\mathbf{B}(\varpi(t^{\prime}))$, such that
$y\Vdash_{t^{\prime}}^{\varpi}x$, $y\in\operatorname{dom}(h\circ
f^{\prime})\cap\operatorname{dom}(g^{\prime})$, and
$f^{\prime}(h(y))=g^{\prime}(y)$, then $x\in\operatorname{dom}(l\circ
f)\cap\operatorname{dom}(g)$ and $g(x)=l(f(x))$.

Note that the computable functions $k\in\mathbf{E}[t^{\prime\prime},t]$ and
$l\in\mathbf{E}[t,t^{\prime\prime}]$ in the above two definitions,
respectively, are not unique.

######  Definition 7 (Fibration-simulation)

We call $\boldsymbol{\varpi}\colon\mathbf{E\rightarrowtriangle B}$ a
fibration-simula-
tion, if for every computable function
$f\in\mathbf{B}\big{[}u,\varpi(t)\big{]}$ there is
$g\in\mathbf{E}[t^{\prime},t]$ cartesian for $f$ and $t$. In this case, we
call $g$ a lift of $f$.

######  Definition 8 (Opfibration-simulation)

We call $\boldsymbol{\varpi}\colon\mathbf{E\to B}$ an opfibration-simulation,
if for every computable function $f\in\mathbf{B}\big{[}\varpi(t),u\big{]}$,
there is $g\in\mathbf{E}[t,t^{\prime}]$ opcartesian for $f$ and $t$. In this
case, we call $g$ a lift of $f$.

###### Example 2

Let $\mathcal{E,B}$ be categories with presheaves $S,S^{\prime}$ and let
$F\colon\mathcal{E\to B}$ be a fibration, such that $S^{\prime}\circ F=S$.
Then,
$\boldsymbol{\gamma}^{F}\colon\operatorname{\mathbf{CM}}^{\operatorname{tot}}(\mathcal{E};S)\operatorname{\rightarrowtriangle}\operatorname{\mathbf{CM}}^{\operatorname{tot}}(\mathcal{B};S^{\prime})$
is a fibration-simulation. To see this, assume we are given a computable
function in
$\operatorname{\mathbf{CM}}^{\operatorname{tot}}(\mathcal{B};S^{\prime})$,
that is a function $S^{\prime}(f)\colon S^{\prime}(b)\to
S^{\prime}(b^{\prime})$, and $e\in\mathcal{E}$ such that
$F(e^{\prime})=b^{\prime}$. As $F$ is a fibration, we find an arrow $g\colon
e\to e^{\prime}$ cartesian over $f$ and $b^{\prime}$ . We show that $S(g)$ is
the desired cartesian function over $S^{\prime}(f)$ and $S(b^{\prime})$. For
this, let functions $S(h),S(h_{2}),S(g_{2})$ as in the following diagram,

${S(e)}$${S^{\prime}(b)}$${S(e^{\prime\prime})}$${S^{\prime}(b^{\prime\prime})}$${S(e^{\prime})}$${S^{\prime}(b^{\prime})}$$\scriptstyle{S(g)}$$\scriptstyle{\Vdash_{e}^{\gamma^{F}}}$$\scriptstyle{S^{\prime}(f)}$$\scriptstyle{S^{\prime}(h)}$$\scriptstyle{S(k)}$$\scriptstyle{S(g_{2})}$$\scriptstyle{\Vdash_{e^{\prime\prime}}^{\gamma^{F}}}$$\scriptstyle{S^{\prime}(h_{2})}$$\scriptstyle{\Vdash_{e^{\prime}}^{\gamma^{F}}}$

be given, where we used that
$\operatorname{\mathbf{CM}}^{\operatorname{prt}}(\mathcal{E};S)(e)=S(e)$ and
$\operatorname{\mathbf{CM}}^{\operatorname{prt}}(\mathcal{B};S^{\prime})(b)=S(b)$,
for every $e$ and $b$, respectively. As $g$ is cartesian over $f$ and
$b^{\prime}$, we obtain an arrow $k\colon e^{\prime\prime}\to e$, such that
$g\circ k=g_{2}$ and $F(k)=h_{2}$. Obviously, $S(k)$ is the function needed,
and hence $S(g)$ is cartesian over $S^{\prime}(f)$ and $S(b^{\prime})$.

###### Proposition 3

If $\mathbf{C}$ is a computability model and
$\gamma\colon\mathbf{C}\to\operatorname{\mathbf{Sets}}$ a simulation, then the
first-projection-simulation
$\operatorname{\mathbf{pr}}_{1}\colon\sum_{\mathbf{C}}\boldsymbol{\gamma}\operatorname{\rightarrowtriangle}\mathbf{C}$
is an opfibration-simulation.

###### Proof

Assume we are given a computable function $f\in\mathbf{C}[t,t^{\prime}]$ and
$\operatorname{\mathsf{pr}}_{1}(t,b)=t$. We need to find some
$b\in\mathbf{C}(t^{\prime})$, such that
$\operatorname{\mathsf{pr}}_{1}(t^{\prime},b^{\prime})=t^{\prime}$, and a
computable function
$f^{\prime}\in\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}\big{[}(t,b),(t^{\prime},b^{\prime})\big{]}$,
such that
$f\Vdash_{((t,b),(t^{\prime},b^{\prime}))}^{\operatorname{\mathsf{pr}}_{1}}f^{\prime}$.
By definition we know that
$f\Vdash_{((t,b),(t^{\prime},b^{\prime}))}^{\operatorname{\mathsf{pr}}_{1}}f^{\prime}$
if and only if $f=f^{\prime}$, so we have to find
$y\in\mathbf{C}(t^{\prime})$, such that $f(b)=b^{\prime}$. For this, we simply
take $b^{\prime}:=f(b)$. To show that $f$ is opcartesian for $f$ and $b$, we
consider the following diagram

${\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t,b)}$${\mathbf{C}(t)}$${\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t^{\prime\prime},b^{\prime\prime})}$${\mathbf{C}(t^{\prime\prime})}$${\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t^{\prime},b^{\prime})}$${\mathbf{C}(t^{\prime})}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{\Vdash_{(t,b)}^{\operatorname{\mathsf{pr}}_{1}}}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{h}$$\scriptstyle{\Vdash_{(t^{\prime\prime},b^{\prime\prime})}^{\operatorname{\mathsf{pr}}_{1}}}$$\scriptstyle{h}$$\scriptstyle{\Vdash_{(t^{\prime},b^{\prime})}^{\operatorname{\mathsf{pr}}_{1}}}$

and we observe that $h$ fills also the triangle on the left, as we have that
$f=h\circ g$ whenever they are defined, so in particular
$f(b)=h\big{(}g(b)\big{)}$, and thus $b^{\prime}=h(b^{\prime\prime})$. Hence,
$h$ is a computable function from
$\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t^{\prime\prime},b^{\prime\prime})$
to
$\Big{(}\sum_{\mathbf{C}}\boldsymbol{\gamma}\Big{)}(t^{\prime},b^{\prime})$.

Next we define split fibration-simulations and split opfibration-simulations.

###### Definition 9

A splitting for a fibration-simulation
$\boldsymbol{\varpi}\colon\mathbf{E\operatorname{\rightarrowtriangle}B}$ is a
rule $\varpi^{\triangle}$ that corresponds a pair $(f,u)$, where
$f\in\mathbf{B}[t_{1},t_{2}]$ and $\varpi(u)=t_{2}$, to a function
$f^{\prime}\in\mathbf{E}[u,u^{\prime}]$ cartesian for $f$ and $u$. This rule
$\varpi^{\triangle}$ is subject to the following conditions:

  * •

For every $f\in\mathbf{B}[t_{1},t_{2}]$ and every
$g\in\mathbf{B}[t_{2},t_{3}]$ we have that

$\varpi^{\triangle}(g\circ
f,u_{1})=\varpi^{\triangle}(g,u_{1})\circ\varpi^{\triangle}(f,u_{2}).$

  * •

For every $t\in T$ we have that
$\varpi^{\triangle}(\mathbf{1}_{\mathbf{B}(t)},u)=(\mathbf{1}_{\mathbf{E}(u)},u).$

A splitting for an opfibration-simulation
$\boldsymbol{\varpi}\colon\mathbf{E\operatorname{\rightarrowtriangle}B}$ is a
rule $\varpi^{\triangle}$ that corresponds a pair $(f,u)$, where
$f\in\mathbf{B}[t_{1},t_{2}]$ and $\varpi(u)=t_{1}$, to a function
$f^{\prime}\in\mathbf{E}[u,u^{\prime}]$ opcartesian over $f$ and $u$. This
rule $\varpi^{\triangle}$ is subject to the following conditions:

  * •

For every $f\in\mathbf{B}[t_{1},t_{2}]$ and every
$g\in\mathbf{B}[t_{2},t_{3}]$ we have that

$\varpi^{\triangle}(g\circ
f,u_{1})=\varpi^{\triangle}(g,u_{2})\circ\varpi^{\triangle}(f,u_{1}).$

  * •

For every $t\in T$ we have that
$\varpi^{\triangle}(\mathbf{1}_{\mathbf{B}(t)},u)=(\mathbf{1}_{\mathbf{E}(u)},u).$

A $($op$)$fibration-simulation $\boldsymbol{\varpi}$ is split, if it admits a
splitting $\varpi^{\triangle}$.

###### Corollary 1

The simulation
$\operatorname{\mathbf{pr}}_{1}\colon\sum_{\mathbf{C}}\boldsymbol{\gamma}\operatorname{\rightarrowtriangle}\mathbf{C}$
is a split opfibration-simulation.

###### Proof

We can simply take $\operatorname{\mathbf{pr}}_{1}^{\triangle}$ to be defined
by the rule $\operatorname{\mathbf{pr}}_{1}^{\triangle}(f,u):=(f,u)$.

##  5 Conclusions and future work

In [9] many concepts and results from category theory were translated to the
theory of computability models, where equalities between arrows are replaced
by certain relations between type names and (partial) computable functions. In
this paper we extended the work initiated in [11, 12] by translating the
Grothendieck construction and the notions of fibration and opfibration within
computability models. The category $\operatorname{\mathsf{CompMod}}$ was shown
to be a type-category, a fact that allows the transport of concepts and facts
from the theory of type-categories to the theory of computability models. For
example, the simulations

$\boldsymbol{\phi}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\sum_{\mathbf{C}}\boldsymbol{\gamma}\
\ ;\ \ \
\mathbf{\operatorname{\mathsf{pr}}_{1}}\circ\boldsymbol{\phi}=\mathbf{1}_{\mathbf{C}}$

are the canonical dependent functions over $\mathbf{C}$ and
$\boldsymbol{\gamma}$ (see also [13], Theorem 4.6). It is natural to search
whether these dependent functions determine a computability model. The
following table includes the correspondences between categorical and
computability model theory-notions presented here.

Category theory Computability model theory category $\mathcal{C}$
computability model $\mathbf{C}$ functor $F\colon\mathcal{C}\to\mathcal{D}$
simulation
$\gamma\colon\mathbf{C}\operatorname{\rightarrowtriangle}\mathbf{D}$ category
of $\operatorname{\mathsf{Sets}}$ computability model of
$\operatorname{\mathbf{Sets}}$ presheaf
$P\colon\mathcal{C}\to\operatorname{\mathsf{Sets}}$ presheaf-simulation
$\gamma\colon\mathbf{C}\operatorname{\rightarrowtriangle}\operatorname{\mathbf{Sets}}$
representable functor $\operatorname{Hom}(a,-)$ representable simulation
$\mathbf{\gamma}_{t_{0}}$ representable functor $\operatorname{Hom}(-,a)$
representable-simulation $\mathbf{\delta}_{t_{0}}$ Grothendieck category
$\sum_{\mathcal{C}}P$ Grothendieck computability model
$\sum_{\mathbf{C}}\boldsymbol{\gamma}$ first-projection functor
$\operatorname{\mathsf{pr}}_{1}\colon\sum_{\mathcal{C}}P\to\mathcal{C}$ first-
projection-simulation
$\mathbf{\operatorname{\mathsf{pr}}_{1}}\colon\sum_{\mathbf{C}}\boldsymbol{\gamma}\operatorname{\rightarrowtriangle}\mathbf{C}$
(op)cartesian arrow (op)cartesian computable function (op)fibration
$\pi\colon\mathcal{E}\to\mathcal{B}$ (op)fibration-simulation
$\boldsymbol{\varpi}\colon\mathbf{E}\operatorname{\rightarrowtriangle}\mathbf{B}$
split (op)fibration split (op)fibration-simulation

It is natural to ask whether the category of presheaves, or more generally of
all functors between two categories, can be translated within computability
models. As a consequence, a Yoneda-type embedding and a corresponding Yoneda
lemma for computability models and appropriate presheaf-simulations can be
formulated. In such a framework the Grothendieck computability model is
expected to have the same crucial role to the proof of a corresponding density
theorem with that of the Grothendieck category to the proof of the categorical
density theorem. For that, we introduce forcing and tracking-moduli in the
definition of a simulation i.e., realisers for the forcing and tracking
relations. A forcing-modulus $\phi^{\gamma}$ for
$\boldsymbol{\gamma}\colon\mathbf{C}\operatorname{\rightarrowtriangle}\mathbf{D}$
is a family of functions

$\phi^{\gamma}:=\big{(}\phi^{\gamma}_{t}\big{)}_{t\in T}\ \ ;\ \ \ \
\phi^{\gamma}_{t}\colon\mathbf{C}(t)\to\mathbf{D}\big{(}\gamma(t)\big{)},$

such that $\phi^{\gamma}_{t}(x)\Vdash^{\gamma}_{t}x$, for every
$x\in\mathbf{C}(t)$. A tracking-modulus $\mu^{\gamma}$ for
$\boldsymbol{\gamma}$ is a family of functions

$\mu^{\gamma}:=\big{(}\mu^{\gamma}_{(s,t)}\big{)}_{s,t\in T}\ \ ;\ \ \ \
\mu^{\gamma}_{(s,t)}\colon\mathbf{C}[s,t]\to\mathbf{D}[\gamma(s),\gamma(t)],$

such that $\mu^{\gamma}_{(s,t)}(f)\Vdash^{\gamma}_{(s,t)}f$, for every
$f\in\mathbf{C}[s,t]$. Conversely, if $\gamma\colon T\to U$, $\phi^{\gamma}$,
and $\mu^{\gamma}$ are typed as above, such that for every
$f\in\mathbf{[}s,t]$ the following rectangle

$\mathbf{D}(\gamma(s))$$\mathbf{D}(\gamma(t))$$\mathbf{C}(t)$$\mathbf{C}(s)$$\mu^{\gamma}_{(s,t)}(f)$
$f$ $\phi^{\gamma}_{s}$ $\phi^{\gamma}_{t}$

with total and partial functions commutes, in the obvious sense, then if we
define $y\Vdash^{\gamma}_{t}x:\Leftrightarrow y=\phi^{\gamma}_{t}(x)$, we get
a realised simulation
$\mathbf{C}\operatorname{\rightarrowtriangle}\mathbf{D}$. We can define then
the exponential computability model with type names the realised simulations.
We hope to elaborate on these concepts in the future.

Our approach to (op)fibration-simulations and (op)cartesian functions is
different from the $2$-categorical approach to fibrations in [16, 18]. In a
subsequent work we expect to show that our approach is equivalent to the
$2$-categorical one.

## References

  * [1] R. Cockett: Categories and Computability, Lecture Notes, 2014.
  * [2] R. Cockett, P. Hofstra: Introduction to Turing categories, Annals of Pure and Applied Logic 156(2-3), 2008, 183–209.
  * [3] R. Cockett, P. Hofstra: Categorical simulations, Journal of Pure and Applied Algebra 214(10), 2010, 1835–1853.
  * [4] J. Cartmell: Generalised algebraic theories and contextual categories, Annals of Pure and Applied Logic, 32, 1986, 209–243.
  * [5] L. Gambarte, I. Petrakis: Categories with a base of computability, in preparation, 2024.
  * [6] J. Longley: Realizability Toposes and Language Semantics, PhD Thesis ECS-LFCS-95-332, University of Edinbourgh, 1995.
  * [7] J. Longley: On the ubiquity of certain total type structures, Mathematical Structures in Computer Science 17(5), 2007, 841–953.
  * [8] J. Longley: Computability structures, simulations and realizability, Mathematical Structures in Computer Science 24(2), 2014, E240201.
  * [9] J. Longley, D. Normann: Higher-Order Computability, Springer 2015.
  * [10] I. Petrakis: Computability models over categories, arXiv:2105.06933v1, 2021.
  * [11] I. Petrakis: Computability models over categories and presheaves, Logical Foundations of Computer Science 2022, S. Artemov, A. Nerode (Eds.), Springer, LNCS 13137, 2022, 253-265.
  * [12] I. Petrakis: Strict computability models over categories and presheaves, Journal of Logic and Computation, exac077, 2022, https://doi.org/10.1093/logcom/exac077.
  * [13] I. Petrakis: Categories with dependent arrows, arXiv:2303.14754v1, 2023.
  * [14] A. M. Pitts: Categorical logic, in S. Abramsky, D. M. Gabbay, T. S. E. Maibaum (Eds.) Handbook of Logic in Computer Science, Vol. 5, Clarendon Press, Oxford, 2000, 39–128.
  * [15] G. Rosolini: Continuity and effectiveness in topoi, PhD Thesis, University of Oxford, 1986.
  * [16] E. Riehl: Two-sided discrete fibrations in 2-categories and bicategories, 2010, available at https://math.jhu.edu/~eriehl/fibrations.pdf.
  * [17] E. Riehl: Category Theory in Context, Dover Publications Inc., 2016.
  * [18] L. Z. Wong: The Grothendieck Construction in Enriched, Internal and $\infty$-Category Theory, PhD Thesis, University of Washington, 2019.


11institutetext:  Jozef Stefan Institute, Jamova 39, 1000 Ljubljana
22institutetext: Jotef Stefan Postgraduate School, Jamova 39, 1000 Ljubljana
22email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Unsupervised Feature Ranking
via Attribute Networks††thanks: Supported by the Slovenian Research Agency
(grant P2-0103 and a young researcher grant), and European Commission (grant
952215).

Urh Primožič 11 0000-0003-1573-7841 Blaž Škrlj 11 2 2 0000-0002-9916-8756 Sašo
Džeroski 11 2 2 0000-0003-2363-712X Matej Petković 11 0000-0002-0495-9046

###### Abstract

The need for learning from unlabeled data is increasing in contemporary
machine learning. Methods for unsupervised feature ranking, which identify the
most important features in such data are thus gaining attention, and so are
their applications in studying high throughput biological experiments or user
bases for recommender systems. We propose FRANe (Feature Ranking via Attribute
Networks), an unsupervised algorithm capable of finding key features in given
unlabeled data set. FRANe is based on ideas from network reconstruction and
network analysis. FRANe performs better than state-of-the-art competitors, as
we empirically demonstrate on a large collection of benchmarks. Moreover, we
provide the time complexity analysis of FRANe further demonstrating its
scalability. Finally, FRANe offers as the result the interpretable relational
structures used to derive the feature importances.

###### Keywords:

feature ranking feature selection unsupervised learning attribute networks
PageRank.

##  1 Introduction

Increasing amounts of high-dimensional data, in fields such as molecular and
systems’ biology, require development of fast and scalable feature ranking
algorithms [14]. By being able to prioritize the feature space with respect to
a given target, feature ranking algorithms already offer, e.g., novel
biomarker candidates. However, the amount of available labeled data is
potentially much smaller when compared to the amount of unlabeled data, which
remains largely unexploited. In response, _unsupervised_ feature ranking
algorithms (that operate only on unlabeled data) are actively developed.

Figure 1: Overview of the FRANe method.

We propose FRANe, a Feature Ranking approach based on Attribute Networks),
schematically shown in Fig. 1. FRANe achieves state-of-the-art performance by
exploiting data-derived relations between the features (which form an
undirected weighted graph). The contributions of this work are manifold, and
can be summarized as follows:

  1. 1.

We propose FRANe, a fast algorithm for unsupervised feature ranking based on
reconstructing attribute networks and subsequent node ranking.

  2. 2.

We demonstrate the algorithm’s state-of-the-art performance on 26 datasets,
validating our claims via Bayesian and classical performance analysis.

  3. 3.

We present an extensive theoretical analysis of the proposed algorithm.

  4. 4.

We offer an implementation of FRANe as a simple-to-use, freely available
Python library, which also includes other baseline approaches.

The remainder of this work is structured as follows. In Section 2, we discuss
the related work that has led us to propose FRANe. We describe the proposed
method in Section 3. Next, we discuss the experimental setup (Section 4),
followed by our results (Section 5) and conclusions (Section 6).

##  2 Related Work

Unsupervised feature ranking is a relatively new research endeavor. An
overview of unsupervised ranking algorithms [13] was published only recently.
Some of the currently well-established methods for unsupervised feature
ranking include: Laplace [8], MCFS, and NDFS. All of them construct a network
of instances by employing an instance similarity measure. Finally, recent work
– awarded the best paper award at ECML PKDD 2019 – uses autoencoder [7]: the
AgnoS-S algorithm gives feature ranking scores as a parameter vector at the
early stages of a neural network, which learns to reconstruct the input space
and assigns each input variable a score as a side-result.

Apart from the unsupervised feature ranking literature, we also draw
inspiration from the literature on _network reconstruction_ and its
applications in gene expression analysis [12, 9, 5]. Network reconstruction
derives a network from a tabular data set, so that relations between instances
(rows) or features (columns) are identified, maintained, and used for a given
down-stream task. Once a tabular data set is converted to a network (graph),
various centrality measures can be used to determine the centrality of the
nodes in the network. Our method uses PageRank centrality measure [11] and its
generalization to weighted graphs. While we use it in the unsupervised fashion
(somewhat similarly to [16]), it can be also used in the supervised scenario
[1].

##  3 Method

Real data often consists of groups of similar features. Intuitively, each such
group has a representative feature that is most similar to all others. This
feature can be expected to predict the values of the other features in the
group reasonably well, making the others redundant. Thus, the most central
features are potentially good candidates for a set of features that a feature
selection algorithm would return. When the number of features in the data goes
into thousands and more, it is expected that many of them are effectively
random noise or completely redundant. The corresponding noisy weights could
prevent discovering the wanted centrality values: We therefore introduce a
minimal weight threshold and only connect the features that are similar
enough.

It is not clear in advance which threshold value is the best. Therefore, we
try out a set of candidate thresholds, following geometric threshold
progression and ranging from the minimal to the maximal edge weight. We
calculate the centrality (feature importance) values from the corresponding
graphs, and obtain a set of feature rankings. Among those, we choose the one
that maximizes the heuristic that is based on the intuition that the feature
importance values in a good ranking have a large spread. Rankings obtained
with low thresholds are expected to be similar, whereas small increases of
high thresholds can cause large changes in the rankings. Sets of candidate
thresholds with few low thresholds and many large ones, e.g., the geometric
threshold sequence, are expected to give good results.

###  3.1 Algorithm

Let $X=[x_{i,j}]_{i,j}\in\mathbb{R}^{m\times n}$ be a data set, where $m$ is
the number of examples and $n$ is the number of features. The $i$-th example
(row in the matrix $X$), $1\leq i\leq m$, is given as
$\bm{x}_{i}=[x_{i,1},\dots,x_{i,n}]$. The $j$-th feature, $1\leq j\leq n$, is
given as a feature vector (column in the matrix $X$)
$\bm{f}_{j}=[x_{1,j},\dots,x_{m,j}]^{T}$.

The computation of FRANe is given in Alg. 1. At input, it takes the (training)
data $X$, a minimal edge threshold and the number of iterations $I$. First, it
computes the feature similarly matrix $W=[w_{j,k}]\in\mathbb{R}^{n\times n}$.
It then computes the geometric sequence $\bm{T}$ of (edge-weight) thresholds
as follows. First, we define the set of similarities between different
features $W^{\prime}=\\{w_{j,k}\mid j\neq k\\}$, together with
$M^{\prime}=\max(W^{\prime})$ and $m^{\prime}=\min(W^{\prime})$. Then, the
dissimilarity values $D=\\{M^{\prime}-w|w\in W^{\prime}\land w<M^{\prime}\\}$
are computed. Finally, the thresholds $t_{i}\in\bm{T}$ are defined as
$\bm{T}=[t_{1},\ldots,t_{I}]$ where

$t_{i}=M^{\prime}-\text{min}(D)\cdot\left(\frac{\text{max}(D)}{\text{min}(D)}\right)^{(i-1)/(I-1)}$
(1)

The temporary resort to dissimilarities is necessary, because we want to
analyze the region of larger similarities more thoroughly. For every threshold
$t_{i}\in\bm{T}$, we build a weighted graph $G(t_{i})$ with $n$ vertices that
correspond to features. An edge with the weight $w_{j,k}$ between $\bm{f}_{j}$
and $\bm{f}_{k}$ exists in $G(t_{i})$, if $w_{j,k}\geq t_{i}$. To avoid too
sparse graphs, we consider only those, for which the average degree
$\bar{e}=|\\{w_{j,k}|j<k\land w_{j,k}\geq t_{i}\\}|/n$ exceeds
$\bar{e}_{\text{min}}=1$.

We run a PageRank on the graph $G(t_{i})$, which returns a possible ranking
$\bm{r}(t_{i})=[\text{PR}(\bm{f}_{1}),\ldots,\text{PR}(\bm{f}_{n})]$, where
$\operatorname{PR}(\bm{f}_{j})$ is the PageRank importance
$\operatorname{PR}{}(j)$ of the node of feature $\bm{f}_{j}$ in $G(t_{i})$, as
defined in [1, 11]. After iterating through all thresholds, calculating the
rankings $\bm{r}(t_{i})$ for each $t_{i}\in\bm{T}$, we pick as output the
ranking with the highest value of the ranking quality heuristic RQH, where

$\text{RQH}(\bm{r})=\frac{\text{second largest score in }\bm{r}}{\text{second
smallest score in }\bm{r}}\text{.}$ (2)

The second largest and smallest scores are taken for stability reasons as the
medians of the three largest and smallest scores, respectively.

$W=$ compute
$[w_{j,k}]_{j,k=1}^{n}=[\mathit{PearsonCorr}(\bm{f}_{j},\bm{f}_{k})+1]_{j,k=1}^{n}$

// $w_{jk}\geq 0$

$S=[]$

// candidate rankings

$\bm{T}=$ list of $I$ thresholds $t_{i}$

// Eq. (1)

1 for  _$t_{i}\in\bm{T}$_ do

$\bar{e}=|\\{w_{j,k}|j,k\land w_{j,k}\geq t_{i}\\}|/n$

// Avoid sparse graphs

2 if  _$\bar{e}\geq\bar{e}_{\text{min}}$_ then

3 $\bm{r}$ = PageRank($G(t_{i})$)

4 add $\bm{r}$ to $S$

5

return $\operatorname{argmax}_{\bm{r}\in S}\operatorname{RQH}(\bm{r})$

// Eq. (2)

Algorithm 1 FRANe($X$, $\bar{e}_{\text{min}}$, $I$)

The first step of the algorithm requires the computation of pairwise
similarities, yielding time complexity of $\mathcal{O}(mn^{2})$. Then, all the
graphs $G(t_{i})$ can be constructed in the total time of
$\mathcal{O}(n^{2})$, if we start with a fully connected graph and then
incrementally remove the edges with the weights on the intervals
$[t_{i-1},t_{i})$. Using the power method for PageRank and assuming that the
number of iterations is upper-bounded with some constant [11], computing
PageRank takes $\mathcal{O}(n^{2})$ steps. Thus, the total number of steps in
the algorithm is $\mathcal{O}(m\cdot n^{2}+I\cdot n^{2})$. Note that the most
time-consuming step (similarity computation) can be easily parallelized, and
that computing PageRank demands only vectorizable matrix-vector multiplication
and vector-vector addition.

##  4 Experimental Setup

In this section, we describe the experimental procedure that we employ to
investigate the following questions: i) How does FRANe compare to state-of-
the-art methods for unsupervised feature ranking, and ii) What is the
influence of the different parameters or FRANe on its performance?

We first give a brief description of the data sets used, continue with the
evaluation procedure and finish with the parametrization of the methods. Note
that the code that allows for replicating our experiments (including the
computation of training and testing splits) is freely available at
https://github.com/FRANe-team/FRANe-dev.

We obtained the data from the Scikit-feature repository [10]. We wanted to use
all the datasets, but had to exclude three data sets from the study
(orlraws10P, lung-small and warpAR10P) to meet the independence assumptions of
the statistical tests. Table 1 gives a more detailed description of the data,
including their domains.

Table 1: Number of features ($n$), examples ($m$) and the domain of the used benchmarks. | $n$ | $m$ | domain |  |  | $n$ | $m$ | domain
---|---|---|---|---|---|---|---|---
gli-85 | 22283 | 85 | biology |  | glioma | 4434 | 50 | biology
smk-can-187 | 19993 | 187 | biology |  | relathe | 4322 | 1427 | text data
cll-sub-111 | 11340 | 111 | biology |  | lymphoma | 4026 | 96 | biology
arcene | 10000 | 200 | mass spectrometry |  | lung | 3312 | 203 | biology
pixraw10p | 10000 | 100 | face image |  | pcmac | 3289 | 1943 | text data
nci9 | 9712 | 60 | biology |  | warppie10p | 2420 | 210 | face image
carcinom | 9182 | 174 | biology |  | colon | 2000 | 62 | biology
allaml | 7129 | 72 | biology |  | coil20 | 1024 | 1440 | face image
leukemia | 7070 | 72 | biology |  | orl | 1024 | 400 | face image
prostate-ge | 5966 | 102 | biology |  | yale | 1024 | 165 | face image
tox-171 | 5748 | 171 | biology |  | isolet | 617 | 1560 | speech recognition
gisette | 5000 | 7000 | digit recognition |  | madelon | 500 | 2600 | artificial
baseshock | 4862 | 1993 | text data |  | usps | 256 | 9298 | drawings

When evaluating the feature ranking algorithms, we follow the approach of [7].
Here, an algorithm is evaluated via 10-fold cross-validation. For a given
partition of a data set into test part (one of the folds) and train part (the
remaining 9 folds), feature ranking is computed on the train part. Then, the
$n^{\prime}$ top-ranked features are selected and the $5$ nearest neighbor
($5$NN) model that uses only these features for predicting the values of all
the features is trained (on the train part of the data). Finally, the
performance of the feature ranking algorithm is measured in terms of the
predictive performance of the $5$NN model on the test set. As evaluation
measure, we use the average relative mean absolute error
$\overline{\operatorname{RMAE}}{}=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m_{\text{TEST}}}\sum_{j=1}^{m_{\text{TEST}}}\frac{\left|\hat{x}_{ij}-x_{ij}\right|}{\sigma(\bm{f}_{i})}$,
where $m_{\text{TEST}}$ is the number of examples in the test set,
$\hat{x}_{ij}$ is the $5$NN’s prediction for $x_{ij}$, and
$\sigma(\bm{f}_{i})=\sqrt{\operatorname{Var}{}(\bm{f}_{i})}$ is the standard
deviation of the feature $\bm{f}_{i}$. A low value of
$\overline{\operatorname{RMAE}}{}$ means that the subset of $n^{\prime}$
chosen features can well reconstruct all the feature values.

The obtained $\overline{\operatorname{RMAE}}{}$ values are averaged over the
$10$ folds. To see how the predictive performance of $5$NN changes as more and
more top-ranked features are considered, one can build a series of $5$NN
models that use $n^{\prime}\in\\{1,2,\dots,2^{k}\\}\cup\\{n\\}$, where
$2^{k}\leq n<2^{k+1}$ features, as shown in Fig. 2. This may be more
informative, but is harder to analyze when comparing different algorithms
through statistical tests. For such comparisons, performance at
$n^{\prime}=16$ is chosen. The hierarchical Bayesian t-test considered in this
work is discussed in more detail in [2]. The test approximates the posterior
probability of the difference in performance between a pair of classifiers.
The posterior plot can be visualized as a simplex, where each point represents
a sample from the posterior distribution. By counting such samples in
different parts of the simplex, the probability of one classifier
outperforming the other is estimated.

The number of iterations in FRANe was set to $I=100$ and the threshold for the
average number of edges was set to $\bar{e}_{\text{min}}=1$. For the decay
factor $\delta$ in PageRank, the recommended value of $\delta=0.85$ was used.
For other algorithms, we used the recommended parameter values. Additionally,
the number of clusters for the methods MCFS and NDFST was set to the number of
classes in the datasets at hand. This was possible since we used
classification datasets from the Scikit-feature repository. The classes were
otherwise ignored.

##  5 Results

In this section, we first report the results of the comparison between FRANe
and its competitors. We then focus on different parts of FRANe and consider
alternative design choices.

The $\overline{\operatorname{RMAE}}{}$ values for the different feature
ranking methods, i.e., the corresponding $5$NN models, are shown in Table 2.

Table 2: The performance (measured in terms of
$\overline{\operatorname{RMAE}}{}$) of $5$NN models that use the
$n^{\prime}=16$ top-ranked features from a given feature ranking. The last two
rows of the table additionally give the average rank of each algorithm and its
number of wins, i.e., the number of times it is ranked first. The best result
in each row is shown in bold.

| FRANe | Laplace | NDFS | Agnos-S | MCFS | SPEC
---|---|---|---|---|---|---
gli-85 | 0.745 | 0.736 | 0.775 | 0.774 | 0.747 | 0.797
smk-can-187 | 0.610 | 0.612 | 0.62 | 0.656 | 0.626 | 0.597
cll-sub-111 | 0.716 | 0.738 | 0.736 | 0.763 | 0.77 | 0.777
arcene | 0.759 | 0.457 | 0.457 | 0.734 | 0.457 | 0.733
pixraw10p | 0.348 | 0.412 | 0.412 | 0.352 | 0.412 | 0.377
nci9 | 0.763 | 0.771 | 0.771 | 0.839 | 0.771 | 0.807
carcinom | 0.719 | 0.739 | 0.751 | 0.743 | 0.717 | 0.743
allaml | 0.711 | 0.726 | 0.747 | 0.775 | 0.744 | 0.749
leukemia | 0.824 | 0.833 | 0.833 | 0.857 | 0.833 | 0.836
prostate-ge | 0.485 | 0.503 | 0.482 | 0.552 | 0.509 | 0.649
tox-171 | 0.725 | 0.77 | 0.785 | 0.734 | 0.776 | 0.781
gisette | 0.440 | 0.481 | 0.481 | 0.509 | 0.481 | 0.533
baseshock | 0.174 | 0.188 | 0.163 | 0.182 | 0.191 | 0.197
glioma | 0.609 | 0.643 | 0.636 | 0.716 | 0.615 | 0.685
relathe | 0.182 | 0.174 | 0.183 | 0.284 | 0.187 | 0.218
lymphoma | 0.774 | 0.873 | 0.873 | 0.804 | 0.873 | 0.873
lung | 0.700 | 0.708 | 0.734 | 0.749 | 0.701 | 0.780
pcmac | 0.156 | 0.147 | 0.160 | 0.168 | 0.147 | 0.163
warppie10p | 0.370 | 0.526 | 0.526 | 0.316 | 0.526 | 0.526
colon | 0.652 | 0.661 | 0.661 | 0.666 | 0.661 | 0.661
coil20 | 0.234 | 0.364 | 0.205 | 0.407 | 0.786 | 0.528
orl | 0.572 | 0.703 | 0.703 | 0.479 | 0.703 | 0.703
yale | 0.608 | 0.749 | 0.749 | 0.572 | 0.749 | 0.749
isolet | 0.567 | 0.548 | 0.562 | 0.523 | 0.619 | 0.643
madelon | 0.853 | 0.856 | 0.856 | 0.86 | 0.856 | 0.856
usps | 0.371 | 0.338 | 0.283 | 0.337 | 0.422 | 0.394
average rank | 1.88 | 2.54 | 2.88 | 4.04 | 3.19 | 4.42
number of wins | 12 | 4 | 5 | 4 | 3 | 1

We can see that FRANe outperforms its competitors. First of all, it has the
best average rank (1.88) among the considered algorithms. The second best
algorithm (in terms of the average rank) is Laplace with an average rank of
2.54. The difference between FRANe and the other algorithms is even more
visible when we compare the numbers of wins: FRANe is the best performing
algorithm in 12 cases (46% win rate). The second highest number of wins (5) is
achieved by NDFS.

To also show some statistical evidence for the quality of the FRANe rankings,
we employ the Bayesian hierarchical t-test [2], since it directly answers
which of the two compared algorithms is better. The other popular option –
frequentist non-parametric tests such as Friedman and Bonferroni-Dunn [6] –
allow for comparison of more than one algorithm, but these tests are typically
too weak (as follows from their definitions [6]), and are harder to interpret.

Figure 2: Error curves for the different rankings on Gisette dataset.

The Bayesian comparison indicates that FRANe dominates its closest competitor
(Laplace), in $26\%$ of the cases, whereas the Laplace method is better in
only $2\%$ of the cases. In the other cases, the difference in performance is
smaller than 0.001 and is considered practically insignificant. This is
consistent with the results in Table 2: the overall win-rate of FRANe is
notably higher (12 against 4), even though these two algorithms differ by less
than one in average rank values. A detailed (and more global) comparison of
the rankings (where the number of chosen features varies from $1$ to $n$) on
Gisette data set is given in Fig. 2. It is clear that the FRANe rankings are
the best as its corresponding curve is below the curves of all other rankings.

###  5.1 Alternative Design Choices

After we have proved that FRANe offers state-of-the-art performance, we now
investigate the sensitivity of its performance to varying its key components.
Due to space constraints, we only vary the similarity measure used in the
computation of the matrix $W$, the threshold progression that defines the list
of edge-weight thresholds $\bm{T}$, and the ranking quality heuristic RQH,
while the node-centrality measure is left fixed (PageRank), and left for
further work. We first give a brief description of the considered threshold
progressions and similarity measures between _different_ features
$W^{\prime}=\\{w_{j,k}\mid j\neq k\\}$, with $m^{\prime}=\min W^{\prime}$, and
$M^{\prime}=\max W^{\prime}$.

#### Similarity measures.

Let
$\bm{f}_{j}=[x_{1,j},\ldots,x_{m,j}],\bm{f}_{k}=[x_{1,k},\ldots,x_{m,k}]\in\mathbb{R}^{m}$
be two feature vectors. Besides correlation, other similarity measures can be
used. They are all based on different distance measures
$d(\bm{f}_{j},\bm{f}_{k})$: i) Canberra
($\sum_{i=1}^{m}\frac{|x_{i,k}-x_{i,j}|}{|x_{i,j}|+|x_{i,k}|}$, ii) Chebyshev
($\max_{i=1}^{m}|x_{i,k}-x_{i,j}|$), iii) Manhattan
($\sum_{i=1}^{m}|x_{i,k}-x_{i,j}|$), and iv) Euclidean
($\left(\sum_{i=1}^{m}|x_{i,k}-x_{i,j}|^{2}\right)^{1/2}$). The corresponding
similarity measures are defined as
$\operatorname{sim}(\bm{f}_{j}\bm{f}_{k})=M^{\prime}-d(\bm{f}_{j}\bm{f}_{k})$.

#### Threshold functions.

The definition of the thresholds $t_{i}$ from Eq. (1) originally follows the
geometric progression. The alternatives are: i)
Linear($m^{\prime},M^{\prime}$), ii)
Linear($\operatorname{mean}(W^{\prime}),M^{\prime}$), iii)
Linear($\operatorname{median}(W^{\prime}),M^{\prime}$), and iv) Quantile,
where $t_{i}=i$-th $I$-quantile of $W^{\prime}$’s for the latter, and
$t_{i}=\frac{b-a}{I-1}(i-1)+a$ for $\textbf{Linear}(a,b)$. The motivation for
using linear progression that starts at the mean (or its more stable analogue
the median) of the $W^{\prime}$ values is that, intuitively, larger thresholds
are more interesting to analyze, since the corresponding graphs are sparser.

The results (see Fig. 3) show that FRANe is quite robust with respect to the
chosen threshold progression and to the chosen similarity measure. Except for
the correlation similarity (works best for 10/26 data sets), and the geometric
threshold progression (works best in 9/26 cases), all the similarity measures
and threshold progressions perform approximately equally well. Still, no fixed
(progression, similarity) pair has more than 3 wins. The detailed results are
available at https://github.com/FRANe-team/FRANe). They also include the
experiments with RQH, where we show that RQH outperforms random search (in
22/26 cases), which is often considered a strong baseline in optimization [3].

Figure 3: Average ranks (over datasets) of different combinations similarity
metric - threshold progression. The legend denotes the average rank of a given
metric-progression combination (the lower, the better).

##  6 Conclusion

In this work we have presented FRANe, an algorithm for network-based
unsupervised feature ranking. In contrast to existing approaches, FRANe
attempts to _reconstruct_ a representative network of _features_. By ranking
_nodes_ in this network via the efficient PageRank approach, we achieve state-
of-the-art results for the task of unsupervised feature ranking.

The results indicate that the proposed unsupervised ranking algorithm is
indeed a strong competitor to the existing approaches. Theoretical analysis
indicates the $\mathcal{O}(n^{2})$ complexity of the distance computation as
one of the main bottlenecks. The current implementation of FRANe, however,
exploits highly optimized compiled routines and scales seamlessly for each of
the considered data sets. An extension which would reduce the quadratic
complexity could include random subspace sampling (where the probability of
choosing a feature depends on its variance).

The proposed methodology is suitable from the interpretability point of view,
as the key nodes (features) and their, e.g., correlation-based neighborhoods
are easily inspected. This can potentially offer novel insights into key parts
of the feature space governing a given data set’s structure.

Given that the main spatial bottleneck is related directly to computation of
PageRank scores (maintaining the graph in the memory), we believe that an
option for further scalability could potentially include distributed storage-
based matrix operations [4, 15], which would facilitate ranking of attributes
when considering very large data sets.

As further work, we believe that distances between features could be also
computed in latent space, where embeddings of features would be first obtained
(via the transposed feature matrix), potentially speeding up the correlation
computation, as well as providing more robust rankings. Furthermore, the body
of work related to _metric learning_ could similarly prove useful when
determining the most suitable similarity score.

## References

  * [1] Backstrom, L., Leskovec, J.: Supervised random walks: Predicting and recommending links in social networks. In: Proceedings of the Fourth ACM International Conference on Web Search and Data Mining. p. 635–644. WSDM ’11, Association for Computing Machinery, New York, NY, USA (2011). https://doi.org/10.1145/1935826.1935914, https://doi.org/10.1145/1935826.1935914
  * [2] Benavoli, A., Corani, G., Demšar, J., Zaffalon, M.: Time for a change: A tutorial for comparing multiple classifiers through bayesian analysis. Journal of Machine Learning Research 18(1), 2653–2688 (2017)
  * [3] Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. Journal of Machine Learning Research 13, 281–305 (2012)
  * [4] Bin Abdullah, I.: Incremental PageRank for Twitter DataUsing Hadoop. Master’s thesis, School of Informatics, University of Edinburgh, Scotland (2010)
  * [5] Chiquet, J., Robin, S., Mariadassou, M.: Variational inference for sparse network reconstruction from count data. In: International Conference on Machine Learning. pp. 1162–1171. PMLR (2019)
  * [6] Demšar, J.: Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research 7, 1–30 (2006)
  * [7] Doquet, G., Sebag, M.: Agnostic feature selection. In: Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, LNCS 11906. pp. 343–358 (04 2020). https://doi.org/10.1007/978-3-030-46150-8_21
  * [8] He, X., Cai, D., Niyogi, P.: Laplacian score for feature selection. In: Proceedings of the 18th International Conference on Neural Information Processing Systems. p. 507–514. NIPS’05, MIT Press, Cambridge, MA, USA (2005)
  * [9] Langfelder, P., Horvath, S.: Wgcna: an r package for weighted correlation network analysis. BMC bioinformatics 9(1), 559 (2008)
  * [10] Li, J., Cheng, K., Wang, S., Morstatter, F., Trevino, R.P., Tang, J., Liu, H.: Feature selection: A data perspective. ACM Computing Surveys (CSUR) 50(6), 94 (2018)
  * [11] Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab (November 1999)
  * [12] Sanguinetti, G., et al.: Gene regulatory network inference: an introductory survey. In: Gene Regulatory Networks, pp. 1–23. Springer (2019)
  * [13] Solorio-Fernández, S., Carrasco-Ochoa, J., Martínez-Trinidad, J.: A review of unsupervised feature selection methods. Artificial Intelligence Review 53, 907–948 (2020)
  * [14] Stańczyk, U., Jain, L.C. (eds.): Feature Selection for Data and Pattern Recognition. Studies in Computational Intelligence, Springer Berlin Heidelberg (2015)
  * [15] Wagle, N., Jasani, S., Gawand, S., Tilekar, S., Patil, P.: Twitter userrank using hadoop mapreduce. In: Proceedings of the ACM Symposium on Women in Research 2016. p. 150–153. WIR ’16, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2909067.2909095, https://doi.org/10.1145/2909067.2909095
  * [16] Zhu, Z., Peng, Q., Guan, X.: Personalized pagerank based feature selection for high-dimension data. In: 2019 11th International Conference on Knowledge and Systems Engineering (KSE). pp. 1–6 (2019)


††thanks: All authors contributed equally to this work.

# Proposal for a fully decentralized blockchain and proof-of-work algorithm
for solving NP-complete problems

Carlos G. Oliver<EMAIL_ADDRESS>School of Computer Science, McGill
University, Montreal, Canada  Alessandro Ricottone  Pericles Philippopoulos
Department of Physics, McGill University, Montreal, Canada

###### Abstract

††preprint: APS/123-QED

_Abstract_ We propose a proof-of-work algorithm that rewards blockchain miners
for using computational resources to solve NP-complete puzzles. The resulting
blockchain will publicly store and improve solutions to problems with real
world applications while maintaining a secure and fully functional transaction
ledger.

##  I Introduction

The widespread success of cryptocurrency platforms such as Bitcoin Nakamoto
(2008), Ethereum Wood (2014) has attracted a substantial amount of
computational resources O’Dwyer and Malone (2014). However, the majority of
this computing power is destined for executing proof-of-work algorithms (for
example, the Bitcoin hashrate is over four exahash per second Red ). While
proof-of-work algorithms are highly reliable, the information generated by
mining does not extend beyond guaranteeing the validity of the information on
the network. In this work, we aim to design a new mining paradigm that diverts
some of the computational resources from mining to solving problems with real
world applications while simultaneously maintaining a secure blockchain.

We focus on the class of problems known as NP-complete problems. Such problems
are most readily applied to blockchain systems because they possess the
important property that the solution to the problem can be verified in
polynomial time, while identifying the solution in the first place has no
known polynomial algorithm. One of the first systems to attempt such a
paradigm was Primecoin King (2013), which in 2013 proposed that users devote
their computational power towards finding specific chains of prime numbers
instead of cryptographic mining. While the identification of prime numbers is
of interest generally, technical limitations force the coin to solve for a
specific type of prime number whose scientific impact is not clear at the
moment. Other blockchains such as the CureCoin fol (2015) (previously known as
Foldcoin) and Coinami Ileri  _et al._ (2016) have attempted to solve
bioinformatics problems which are of more direct impact. However, both systems
depend on a central authority to delegate the problems and validate the
identity of users who must register. We therefore aim at developing a
cryptocurrency that addresses these shortcomings while still reliably acting
as a trusted distributed ledger. The key components we aim to implement are:

  * •

Full decentralization

  * •

Anonymity

  * •

Generation of solutions to practical problems

By proposing a novel mining and incentive protocol to the established Bitcoin
framework, we believe we have achieved a system that satisfies all of the
above features.

##  II Blockchain

The proposed blockchain is based closely on the well established Bitcoin
blockchain protocol, with one key difference: miners are rewarded for solving
an NP-complete problem via a mining difficulty reduction. The idea is that
miners, after building a block are allowed to choose between submitting a
block mined using the standard Bitcoin protocol (see Nakamoto (2008)) by
finding a valid nonce, or if they have computed an improved solution to an NP-
complete problem can publish it along with their block which would be verified
and accepted by the network at a reduced difficulty.

For the sake of simplicity, we assume that the blockchain will deal with a
single instance of a given NP-complete problem, we call this problem $P$. For
example, if the NP-complete problem were finding a graph coloring (GC) of a
graph $g$ of size less than some current best $k$, the blockchain would only
work on that specific $g$ and $P:=(g,k)$. In Section III we discuss ways to
incorporate a greater number of instances of the problem. The only requirement
for a problem to be used in the proof-of-work is that verifying a solution to
the problem can be accomplished in polynomial time with a clearly defined
scoring scheme.

###  II.1 Block structure

Blocks are structured identically to Bitcoin blocks (i.e. Transaction Merkle
Root, miner address, nonce, etc.), with the addition of a new field for
storing the problem, $P$. The genesis block is special in that it contains a
field that stores the initial problem state. For example, if the blockchain is
to solve the Traveling Salesman Problem (TSP), the block will simply store the
graph to be worked on. Typically such problems can be compactly represented in
matrix form.

Subsequent blocks contain a field that stores a compact representation of a
solution. In the case of TSP, this would be a vector with the index of visited
nodes. However, not all blocks are forced to contribute a solution to the
given problem, and this field is allowed to take on a null value that
indicates that the miner produced the block normally.

###  II.2 Incentivization

The main task a Bitcoin miner has to accomplish in order to produce a valid
block once he has obtained a set of valid transactions is to find a valid
nonce, $n$. More specifically, miners need to find an integer $n$ such that

$H(B,n)<\epsilon_{d},$ (1)

where $H(B,n)$ is the hash function applied to block $B$ and $n$, and
$\epsilon_{d}$ is the target associated with difficulty $d$. Because $H$ is a
cryptographic hash function, the output of $H$ is completely unpredictable,
therefore mining consists of brute forcing values of $n$ until the condition
is satisfied. Clearly an $\epsilon_{d}$ with smaller $d$ is easier to satisfy
than the inverse. Once a miner finds a valid nonce they can publish the block
along with the $n$ and the network can easily verify the validity of the block
according to the network’s current difficulty $d$. Because mining is a
competitive endeavor, we reward miners that compute solutions to $P$ by
reducing mining difficulty. In our protocol, miners will accept blocks that
satisfy a reduced difficulty $d_{r}$ constraint if the block contains a
solution that is better than the current best solution on the blockchain. If
the average time needed to mine a block _with_ a solution is shorter than the
average time needed to mine a block _without_ , we expect miners to spend
their computational power in improving the solution to the problem.

###  II.3 Mining & Difficulty Scaling

In Bitcoin, the hashing difficulty is retargetted every $N$ $(=2016)$ blocks,
by comparing the time it took to mine these blocks, $T^{\star}$, to a target
time $T$. In the proposed blockchain, we have two different difficulties which
must each be retargetted. These difficulties are $d_{b}$, for blocks mined
_without_ a solution to problem $P$, and $d_{r}$, a reduced difficulty for
blocks mined _with_ a solution to problem $P$. For the retargetting of both
difficulties to be accomplished, a value for $T$ must be fixed by the
blockchain, as is the case for Bitcoin. However, we must also establish the
constant $0<\eta<1$, which represents the desired ratio of time it takes to
mine a block with a solution to problem $P$, $t_{s}$, to the time it takes to
mine a block without a solution to problem $P$, $t_{b}$. A smaller $\eta$
would result in a greater incentive for puzzle solutions to be found.

We define $t_{s}^{\star}$ to be the average time it took to mine a block with
a solution to problem $P$ and $t_{b}^{\star}$ to be the average time it took
to mine a block without a solution to problem $P$. We can thus write these two
quantities as

$\displaystyle t_{s}^{\star}=\frac{d_{r}}{p_{H}}+\frac{d_{p}}{p_{H}},$ (2)
$\displaystyle t_{b}^{\star}=\frac{d_{b}}{p_{H}},$ (3)

where $p_{H}$ is the rate at which computations can be performed by the
network, and $d_{p}$ is the difficulty associated with solving the problem
$P$. We expect $d_{p}$ to increase with time as better and better solutions to
problem $P$ are found. We also define the _measured_ quantity,
$\eta^{\star}=t_{s}^{\star}/t_{b}^{\star}$ and $b$, the fraction of blocks
mined with base difficulty $d_{b}$. Using Eqs. (2) and (3),

$\eta^{\star}=\frac{d_{r}+d_{p}}{d_{b}}.$ (4)

The goal, after $N$ blocks, is to set $d_{r}$ and $d_{b}$ to new values
$d_{r}^{\prime}$ and $d_{b}^{\prime}$ so that the time it takes to mine the
$N$ blocks, $T^{\star}$, under fixed $p_{H}$, $d_{p}$ and $b$, readjusts
towards the target $T$ and $\eta^{\star}$ readjusts towards $\eta$. We can
therefore write

$\displaystyle
T^{\star}=\frac{N}{p_{H}}d_{b}\left[b+(1-b)\eta^{\star}\right],$ (5)
$\displaystyle T=\frac{N}{p_{H}}d_{b}^{\prime}\left[b+(1-b)\eta\right].$ (6)

Solving these equations for the retargetted base difficulty yields,

$d_{b}^{\prime}=d_{b}\left[\frac{b+(1-b)\eta^{\star}}{b+(1-b)\eta}\right]\frac{T}{T^{\star}}.$
(7)

To retarget $d_{r}$ we use the fact that the difficulties should be updated so
that

$\eta=\frac{d_{r}^{\prime}+d_{p}}{d_{b}^{\prime}}.$ (8)

We note that $d_{p}$ is not retargetted to $d_{p}^{\prime}$ as it is
completely determined by the status of the problem $P$. Combining Eq. (8) with
Eqs. (2) and (3), we can write

$d_{r}^{\prime}-d_{r}=\eta d_{b}^{\prime}-\eta^{\star}d_{b}.$ (9)

Thus, Eqs. (7) and (9) display the rules for the difficulty retargetting of
the proposed blockchain. As with the Bitcoin blockchain, it would be advisable
to introduce a maximum retargetting factor (4 for the Bitcoin chain) to avoid
a change in difficulty that is too abrupt. In other words, we would enforce

$\frac{1}{4}\leq\frac{d_{b}^{\prime}}{d_{b}}\leq 4.$ (10)

After $P$ has become too difficult to improve, it is possible that
$d_{p}>d_{b}$. This implies that the updated difficulty $d_{r}^{\prime}$
becomes negative at which point it would be necessary to introduce a new
problem $P$ to work on. We discuss how this can be implemented in Section III.
However, at the point when it is no longer worthwhile to solve the puzzle, the
blockchain naturally functions with $d_{b}$ and the standard Bitcoin proof-of-
work.

###  II.4 Possible Puzzles

There is a wealth of interesting NP-complete problems that could be used as
puzzles for the blockchain. Here we suggest a list, which is by no means
exhaustive, of possible applications:

  * •

Multiple Sequence Alignment: many databases with DNA sequence information are
widely available (e.g. Sherry  _et al._ (2001)). The problem of improving
aligned multiple DNA sequences is NP-complete and has many applications in
biology and medicine.

  * •

Protein/biomolecule folding and design: computing the 2D and 3D geometry of
chains of DNA/RNA/Protein as well as designing sequences with desired
geometries. Many databases for this problem are also available, e.g. Protein
Data Bank Berman  _et al._ (2006). Solutions so this problem can have direct
medical applications.

  * •

Ising-lattice: The decision form of the Ising model (to decide whether the
ground state of an Ising Hamiltonian has energy $E\leq 0$) is NP-complete
Lucas (2013) and it can be mapped to many other NP-complete problems. These
models are widely studied in physics.

##  III Multiple-Puzzle Blockchain

Figure 1: Potential blockchain architecture for handling multiple puzzles.
Problem set $\Omega$ is stored in independent storage nodes with addresses S1
and S2 (lower left) that sync to the main blockchain (top). Worker nodes N1,
N2, N3, that mine coins and solve puzzles request puzzle data from the storage
nodes. The index(es) $i$ of the admissible puzzle(s) for block $B_{t+1}$ are
obtained from the hash of the block $H(B_{t})$, which is also contained in
$B_{t+1}$. The hash-determined problem index is an optional feature and can be
omitted if the blockchain allows any problem solution to be accepted at any
time. Once a miner has successfully mined a block with transactions Tx by
finding a valid nonce n and puzzle solution $w_{t+1}$ he publishes the block
to the network.

Clearly a blockchain that only works on a single problem, $P$ will quickly
exhaust its usefulness. Ideally, we would want the blockchain to
simultaneously solve a set $\Omega\subseteq\Omega_{j}$ of instances of an NP-
complete problem $j$, where $i$ is an index over all possible NP-complete
problems, $j\in\\{\mathrm{GC},\mathrm{TSP},\dots\\}$, and $\Omega_{j}$
contains all possible NP-complete problems of type $j$. While we leave the
specifics of how this can be achieved to future work, here we discuss some of
the challenges and potential solutions.

###  III.1 Puzzle Storage

Because we wish to have full decentralization, $\Omega$ must be stored on the
blockchain. This can be achieved in one of two manners. If the size of
$\Omega$ is small enough to be stored by all the miners, the genesis block
could simply be used to store an indexed database of $\Omega$. Subsequent
blocks that contain solutions to a problem $P\in\Omega$ would simply include
with their solution a pointer to the corresponding problem in the genesis
block. If $\Omega$ is too large for all the miners to store, the network could
instead allow some nodes to participate as ‘storage’ nodes and collect a
reward for doing so in a manner similar to file storage coins Fil . The main
blockchain would then simply contain pointers to the relevant problem for each
block (Fig. 1, lower half).

###  III.2 Puzzle Selection

In the single-puzzle blockchain, miners always work on the same problem. In
the multiple-puzzle setting there must be a protocol for selecting the problem
for the current block. The most natural approach is to allow miners to submit
a solution to any $P\in\Omega$ they choose for a reduced difficulty. This has
the advantage of potentially maximizing the network’s efficiency in solving
problems if miners work on non-overlapping regions of $\Omega$. However, if
one wishes to force some distribution on the frequency that each puzzle gets
included in a block, one could use the hash of the previous block to determine
the index $j$ of the current admissible puzzle, $P_{i}\in\Omega$. (Fig. 1,
upper half) Such a function could be augmented for example to favor problems
not yet been included and suppress problems that have been worked on too much.

###  III.3 New Puzzles

Eventually (unless $\Omega$ is very large), all puzzles will reach some
plateau of optimality and further computation will not produce significant
gains. The obvious solution to this situation is to allow the blockchain to
incorporate new problems into $\Omega$. The challenge is to manage new puzzle
incorporation without a central authority that ensures problems are: 1) valid
instances of $j$ 2) of interest 3) not already solved. New puzzles can be
included as a special transaction. This transaction can store the problem in
the current block, or add it to the storage nodes. To discourage puzzles that
do not satisfy the three criteria, new problems should be submitted with a fee
which is then distributed as a reward to miners that solve the puzzle.
Alternatively, the network can agree on a new problem set off-chain and in a
manner similar to Bitcoin, induce a fork or upgrade of the chain that includes
a new agreed upon problem set.

##  IV Conclusion

We have outlined the major components of a cryptocurrency system that
incentivizes the identification of solutions to scientifically interesting
problems without relying on any central authorities or servers. The benefit of
using this proposed blockchain instead of other proof-of-work blockchains is
twofold. A portion of the power expended on hashing is redirected to solving
problems that are scientifically relevant. And second, solutions to these
problems are naturally stored and updated in the blockchain for public access.
To our knowledge, this is the first blockchain solution that achieves these
features in a fully decentralized manner. The implementation of this system is
left for future work.

## References

  * Nakamoto (2008) S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” (2008).
  * Wood (2014) G. Wood, Ethereum Project Yellow Paper 151 (2014).
  * O’Dwyer and Malone (2014) K. J. O’Dwyer and D. Malone, (2014).
  * (4) “Bitcoin Hash Rate,” https://news.bitcoin.com/bitcoin-hashrate-four-exahash-per-second/, accessed: .
  * King (2013) S. King, July 7th (2013).
  * fol (2015) “Curecoin whitepaper,” http://foldingcoin.net/the-coin/white-paper/ (2015), accessed:.
  * Ileri  _et al._ (2016) A. M. Ileri, H. I. Ozercan, A. Gundogdu, A. K. Senol, M. Y. Ozkaya, and C. Alkan, arXiv preprint arXiv:1602.03031 (2016).
  * Sherry  _et al._ (2001) S. T. Sherry, M.-H. Ward, M. Kholodov, J. Baker, L. Phan, E. M. Smigielski, and K. Sirotkin, Nucleic acids research 29, 308 (2001).
  * Berman  _et al._ (2006) H. M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. N. Bhat, H. Weissig, I. N. Shindyalov, and P. E. Bourne, in  _International Tables for Crystallography Volume F: Crystallography of biological macromolecules_ (Springer, 2006) pp. 675–684.
  * Lucas (2013) A. Lucas, arXiv preprint arXiv:1302.5843 (2013).
  * (11) “FileCoin whitepaper,” https://filecoin.io/filecoin.pdf, accessed: .