14
$\begingroup$

This question is inspired by a comment Jukka Suomela made on another question.

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Huck Bennett Dec 6 '11 at 21:27
  • $\begingroup$ @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. $\endgroup$ – Aaron Sterling Dec 6 '11 at 21:43
13
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Finding the next generation of a Cellular Automaton.

This can be solved as you described in constant time. $\;$ (i.e., independent of the input)

$\endgroup$
  • $\begingroup$ I think more care is needed to actually formulate a (non-trivial, interesting) computational problem that is solvable in finite time using cellular automata? $\endgroup$ – Jukka Suomela Dec 6 '11 at 20:30
  • 1
    $\begingroup$ I agree with @Jukka. I consider the current version of this answer to be at the level of a comment, and not an informative one. It does not describe either a computational problem or an algorithm. Downvoted. $\endgroup$ – Aaron Sterling Dec 6 '11 at 20:52
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Dec 8 '11 at 7:22
  • 1
    $\begingroup$ @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. $\endgroup$ – Aaron Sterling Dec 8 '11 at 16:16
0
$\begingroup$

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$."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.