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?

Question

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.

Answer 1

This function is not necessarily total, even when the set of edges is decidable. Note that you haven't proved it, but simply showed why we can't directly use some classic algorithm for finite graphs, though perhaps some smarter algorithm exists?

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).