<p>Essentially, every problem that is at least as hard as coloring requires an algorithm with a running time dependent on the number of nodes in the network and thus cannot work in an infinite but locally finite graph. This follows from Linial's seminal <a href="http://www.cs.huji.ac.il/~nati/PAPERS/locality_dist_graph_algs.pdf" rel="nofollow">log*n lower bound.</a></p>

CC BY-SA 3.0
2011-12-08T07:22:53.307Z
But what precisely is your model of computation here? Linial assumes that all nodes have unique numerical identifiers; if we try to map it into the setting suggested in the original question, we would have Turing machines that are given their numerical identifiers on their input tapes. But now the size of the identifier is unbounded; merely waiting until all machines have read their own identifiers takes infinitely long. I would argue that the obstacle is not really Linial's lower bound, but it is the model of computation: unique identifiers are the wrong model when we deal with infinities.
Jukka Suomela
CC BY-SA 3.0
2011-12-08T16:16:11.087Z
@Jukka: I had imagined a system where all the processors were anonymous when I wrote the question, exactly to avoid ID's that grow without bound. But it now seems to me there may be a nontrivial issue here. If you choose a program-size and some computable function that bounds the size of any processor's neighborhood, then perhaps the all-powerful adversary can choose a large-but-finite set of IDs so that Linial's limit is still a factor somehow. The adversary may need to be able to compute a function that grows faster than any computable function to do this though.
Aaron Sterling
CC BY-SA 3.0
2011-12-08T04:29:34.497Z
2011-12-08T04:29:34.497Z
Peter
<p>This doesn't quite fit your definition, but I think only because of non-uniformity. Before showing parity was not in $AC^0$, Sipser (I believe it was) showed that any infinite parity function (a function on countably many variables that changes output whenever any single input is changed) could not be solved in "infinitary $AC^0$."</p>

CC BY-SA 3.0
2016-09-30T22:37:37.380Z
2016-09-30T22:37:37.380Z
Joshua Grochow
<p>Just to give some ideas of what is possible (but somewhat non-trivial), here is one example: a distributed algorithm that finds a <strong>maximal edge packing</strong> on a bounded-degree graph.</p>

<h2>Problem definition</h2>

<p>Given a simple undirected graph $G = (V,E)$, an <em>edge packing</em> (or fractional matching) associates a weight $w(e)$ with each edge $e \in E$ such that for each node $v \in V$, the total weight of edges incident to $v$ is at most $1$. A node is <em>saturated</em> if the total weight of incident edges is equal to $1$. An edge packing is <em>maximal</em> if all edges have at least one saturated endpoint (i.e., none of the weights can be greedily extended).</p>

<p>Observe that a maximal matching $M \subseteq E$ defines a maximal edge packing (set $w(e) = 1$ iff $e \in M$); hence it is easy to solve in a classical centralised setting (assuming $G$ is finite).</p>

<p>Edge packings actually have some applications, at least if one defines an application in the usual TCS sense: the set of saturated nodes forms a $2$-approximation of a minimum vertex cover (of course this makes only sense in the case of a finite $G$).</p>

<h2>Model of computation</h2>

<p>We will assume that there is a global constant $\Delta$ such that the degree of any $v \in V$ is at most $\Delta$.</p>

<p>To keep this as close to the spirit of the original question, let us define the model of computation as follows. We assume that each node $v \in V$ is a Turing machine, and an edge $\{u,v\} \in E$ is a communication channel between $u$ and $v$. The input tape of $v$ encodes the degree $\deg(v)$ of $v$. For each $v \in V$, the edges incident to $v$ are labelled (in an arbitrary order) with integers $1,2,\dotsc,\deg(v)$; these are called <em>local edge labels</em> (the label of $\{u,v\} \in E$ can be different for $u$ and $v$). The machine has instructions with which it can send and receive messages through each of these edges; a machine can address its neighbours by using the local edge labels.</p>

<p>We require that the machines compute a valid edge packing $w$ for $G$. More precisely, each $v \in V$ has to print on its output tape an encoding of $w(e)$ for each edge $e$ incident to $v$, ordered by the local edge labels, and then halt.</p>

<p>We say that a distributed algorithm $A$ finds a maximal edge packing in time $T$, if the following holds for any graph $G$ of maximum degree $\Delta$, and for any local edge labelling of $G$: if we replace each node of $G$ with an identical copy of the Turing machine $A$ and start the machines, then after $T$ steps all machines have printed a valid (globally consistent) solution and halted.</p>

<h2>Infinities</h2>

<p>Now all of the above makes perfect sense even if the set of nodes $V$ is countably infinite.</p>

<p>The problem formulation and the model of computation do not have any references to $|V|$, directly or indirectly. The length of the input for each Turing machine is bounded by a constant.</p>

<h2>What is known</h2>

<p>The problem can be solved in finite time even if $G$ is infinite.</p>

<p>The problem is non-trivial in the sense that some communication is necessary. Moreover, the running time depends on $\Delta$. However, for any fixed $\Delta$, the problem can be solved in constant time regardless of the size of $G$; in particular, the problem is solvable on infinitely large graphs.</p>

<p>I have not checked what is the best known running time in the model defined above (which is <em>not</em> the usual model used in the field). Nevertheless, a running time that is polynomial in $\Delta$ should be fairly easy to achieve, and I think a running time that is sublinear in $\Delta$ is impossible.</p>

CC BY-SA 3.0
2011-12-06T22:26:11.747Z
2011-12-06T22:26:11.747Z
Jukka Suomela
<p>This question is inspired by a comment Jukka Suomela made on <a href="https://cstheory.stackexchange.com/q/9310/30">another question</a>.</p>

<blockquote>
  <p>What are examples of infinitely large but locally finite computation problems (and algorithms)?</p>
</blockquote>

<p>In other words, what are examples of computations that halt in finite time, in which each Turing Machine reads and processes only finite data, but altogether the computation solves an infinite-size problem if there are infinitely-many Turing machines networked together?</p>

CC BY-SA 3.0
2011-12-06T21:27:58.470Z
I was going to comment that this idea seems the same as a single TM with infinitely many tapes, which I thought I'd seen before, but now I can't find a reference. Am I dreaming or is this an explored idea? Certainly other hypercomputation extensions like infinite time TMs have been studied. Does the idea of TM "networking" add anything to this model?
Huck Bennett
CC BY-SA 3.0
2011-12-06T21:43:01.437Z
@HuckBennett: I don't know; it might be the same.  I got the sense from Jukka's original comment that he was thinking about problems like Graph Coloring on an infinite graph of bounded degree (though I don't know whether that particular problem would be an answer to this question).  Each TM would run the same algorithm, and talk to a finite set of neighbors.  It seems that a TM with infinitely-many tapes might be able to simulate a graph with infinitely-many edges between two nodes, which is different in principle from what I have in mind. I know very little about such models though.
Aaron Sterling
<dc.distributed-comp>
Infinitely large but locally finite computation problems
Aaron Sterling
# Infinitely large but locally finite computation problems

(Asked by: username_0 on 2011-12-06)

This question is inspired by a comment username_3 made on [another question](https://cstheory.stackexchange.com/q/9310/30).

> What are examples of infinitely large but locally finite computation problems (and algorithms)?

In other words, what are examples of computations that halt in finite time, in which each Turing Machine reads and processes only finite data, but altogether the computation solves an infinite-size problem if there are infinitely-many Turing machines networked together?

**Tags:** dc.distributed-comp

> **Comments:**
> **username_1**: I was going to comment that this idea seems the same as a single TM with infinitely many tapes, which I thought I'd seen before, but now I can't find a reference. Am I dreaming or is this an explored idea? Certainly other hypercomputation extensions like infinite time TMs have been studied. Does the idea of TM "networking" add anything to this model?  
> **username_0**: @HuckBennett: I don't know; it might be the same.  I got the sense from Jukka's original comment that he was thinking about problems like Graph Coloring on an infinite graph of bounded degree (though I don't know whether that particular problem would be an answer to this question).  Each TM would run the same algorithm, and talk to a finite set of neighbors.  It seems that a TM with infinitely-many tapes might be able to simulate a graph with infinitely-many edges between two nodes, which is different in principle from what I have in mind. I know very little about such models though.  

---

## 3 answers

### Answer by username_3 on 2011-12-06. Score: 13 | Accepted answer

Just to give some ideas of what is possible (but somewhat non-trivial), here is one example: a distributed algorithm that finds a **maximal edge packing** on a bounded-degree graph.

## Problem definition

Given a simple undirected graph $G = (V,E)$, an *edge packing* (or fractional matching) associates a weight $w(e)$ with each edge $e \in E$ such that for each node $v \in V$, the total weight of edges incident to $v$ is at most $1$. A node is *saturated* if the total weight of incident edges is equal to $1$. An edge packing is *maximal* if all edges have at least one saturated endpoint (i.e., none of the weights can be greedily extended).

Observe that a maximal matching $M \subseteq E$ defines a maximal edge packing (set $w(e) = 1$ iff $e \in M$); hence it is easy to solve in a classical centralised setting (assuming $G$ is finite).

Edge packings actually have some applications, at least if one defines an application in the usual TCS sense: the set of saturated nodes forms a $2$-approximation of a minimum vertex cover (of course this makes only sense in the case of a finite $G$).

## Model of computation

We will assume that there is a global constant $\Delta$ such that the degree of any $v \in V$ is at most $\Delta$.

To keep this as close to the spirit of the original question, let us define the model of computation as follows. We assume that each node $v \in V$ is a Turing machine, and an edge $\{u,v\} \in E$ is a communication channel between $u$ and $v$. The input tape of $v$ encodes the degree $\deg(v)$ of $v$. For each $v \in V$, the edges incident to $v$ are labelled (in an arbitrary order) with integers $1,2,\dotsc,\deg(v)$; these are called *local edge labels* (the label of $\{u,v\} \in E$ can be different for $u$ and $v$). The machine has instructions with which it can send and receive messages through each of these edges; a machine can address its neighbours by using the local edge labels.

We require that the machines compute a valid edge packing $w$ for $G$. More precisely, each $v \in V$ has to print on its output tape an encoding of $w(e)$ for each edge $e$ incident to $v$, ordered by the local edge labels, and then halt.

We say that a distributed algorithm $A$ finds a maximal edge packing in time $T$, if the following holds for any graph $G$ of maximum degree $\Delta$, and for any local edge labelling of $G$: if we replace each node of $G$ with an identical copy of the Turing machine $A$ and start the machines, then after $T$ steps all machines have printed a valid (globally consistent) solution and halted.

## Infinities

Now all of the above makes perfect sense even if the set of nodes $V$ is countably infinite.

The problem formulation and the model of computation do not have any references to $|V|$, directly or indirectly. The length of the input for each Turing machine is bounded by a constant.

## What is known

The problem can be solved in finite time even if $G$ is infinite.

The problem is non-trivial in the sense that some communication is necessary. Moreover, the running time depends on $\Delta$. However, for any fixed $\Delta$, the problem can be solved in constant time regardless of the size of $G$; in particular, the problem is solvable on infinitely large graphs.

I have not checked what is the best known running time in the model defined above (which is *not* the usual model used in the field). Nevertheless, a running time that is polynomial in $\Delta$ should be fairly easy to achieve, and I think a running time that is sublinear in $\Delta$ is impossible.


---

### Answer by username_2 on 2011-12-08. Score: 2

Essentially, every problem that is at least as hard as coloring requires an algorithm with a running time dependent on the number of nodes in the network and thus cannot work in an infinite but locally finite graph. This follows from Linial's seminal [log\*n lower bound.](http://www.cs.huji.ac.il/~nati/PAPERS/locality_dist_graph_algs.pdf)

> **Comments:**
> **username_3**: But what precisely is your model of computation here? Linial assumes that all nodes have unique numerical identifiers; if we try to map it into the setting suggested in the original question, we would have Turing machines that are given their numerical identifiers on their input tapes. But now the size of the identifier is unbounded; merely waiting until all machines have read their own identifiers takes infinitely long. I would argue that the obstacle is not really Linial's lower bound, but it is the model of computation: unique identifiers are the wrong model when we deal with infinities.  
> **username_0**: @Jukka: I had imagined a system where all the processors were anonymous when I wrote the question, exactly to avoid ID's that grow without bound. But it now seems to me there may be a nontrivial issue here. If you choose a program-size and some computable function that bounds the size of any processor's neighborhood, then perhaps the all-powerful adversary can choose a large-but-finite set of IDs so that Linial's limit is still a factor somehow. The adversary may need to be able to compute a function that grows faster than any computable function to do this though.  

---

### Answer by username_4 on 2016-09-30. Score: 0

This doesn't quite fit your definition, but I think only because of non-uniformity. Before showing parity was not in $AC^0$, Sipser (I believe it was) showed that any infinite parity function (a function on countably many variables that changes output whenever any single input is changed) could not be solved in "infinitary $AC^0$."


---

