# Let $G = (V,E)$ be an infinite digraph: $E \subset \mathbb{N}\times \mathbb{N}$ is decidable. Does it imply that $\delta (i,j)$ is a total function?

Problem:

Let $G = (V,E)$ be an infinite digraph, such that $V = \mathbb{N}$, and $E \subset \mathbb{N}\times \mathbb{N}$ is decidable set. Does it imply that $\delta (i,j)$ is a total function?

*(where $\delta (i,j)$ is the shortest path function between vertex $i$ and $j$).

I'm having a hard time trying to understand the problem, so any help would be appreciate.

Well, this is what I know (hopefully I'm not misunderstanding anything here):

A language (or set) $L$ is decidable if $\exists$ and algorithm $A$, such that if $v \in L$, then $A(v) = \text{Accept}$ and halts and if $v\not\in L$, then $A(v) = \text{Reject}$ and halts.

A function $f$ is total if $\exists$ and algorithm $B$ that computes it $\forall v\in \mathrm{Dom}(f)$ and always halts.

My attempt:

Suppose $\delta (i,j)$ is a total function and let algorithm $B$ be the Bellman-Ford algorithm ($BFA$).

The relaxation step in $BFA$ is given by

// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u


Because $|V| = \infty$ we have that the algorithm never halts, since size(vertices) - 1 $= |V| -1 = \infty$. This implies that $BFA$ doesn't compute $\delta (i,j) \implies \delta (i,j)$ is not a total function (So, to my understanding it would be only a partial function, since $\exists$ some vertices $u,\ v$ for which the function $\delta (u,v)$ is undefined).

Although to me at first glance it makes kind of sense, I guess I'm wrong, mainly because I didn't consider the fact that $E$ is a decidable set.

Imagine $G$ is a "universal configuration graph". To explain what i mean, lets first discuss what is the configuration graph of a Turing machine $M$. Given a Turing machine $M$, let $G_{M}$ denote the graph whose vertices are configurations of the form $C=(q,s_1,s_2)$ where $q$ is the machine state, and $s_1,s_2$ are the strings to the right and left of the read/write head correspondingly (the first symbol of $s_2$ is the current symbol under examination). $(C_1,C_2)\in E$ if you can go from $C_1$ to $C_2$ in a single step. The number of vertices in $G_M$ is countable (since we go over all possible contents of the tape).
Now I want to define $G$ as $\bigcup\limits_{M} G_{M}$. The graph $G$ is the disjoint union of all possible configuration graphs (so we go over all Turing machines, note that the number of vertices remains countable). To identify each vertex (configuration) in $G$ to the graph $G_{M}$ it's belonging to, we can add the encoding of the machine to the description of each vertex. The set of edges of $G$ is clearly decidable, since given two vertices $v_1=\left(\langle M\rangle , C_1\right)$ and $v_2=\left(\langle M'\rangle , C_2\right)$, we check if $\langle M\rangle=\langle M' \rangle$, and if so, we check if $M$'s transition function allows us to move from $C_1$ to $C_2$ in a single step.
If reachability in $G$ is decidable, then you can decide the halting problem. Given a Turing machine $M$ and input $x$, check if the accepting configuration of $M$ is reachable from the initial configuration of $M$ on input $x$ (for simplicity, you can assume there is a unique accepting configuration).