Wire-crossing problem

The wire-crossing problem, in its general form, states that some programs in some languages cannot be represented as planar graphs (that is, graphs with edges that do not cross when rendered in two dimensions.) It was (as far as we are aware) first considered for Befunge, with respect to the necessity of the # operator.

Strong claim

The strong claim for the problem would be that a non-planar graph is required for Turing-completeness - that is, if some language L forbids the construction of programs which are non-planar graphs, then there are some problems that a Turing machine can solve that that L cannot.

There are some definite problems with testing the strong claim, not the least of which are:

• how to consistently define a language as a graph, and
• what properties of that graph might be retained or lost when one language is transformed into another, even if the two languages are in the same computational class.

Languages as graphs

It is quite straightforward to represent a finite-state automaton as a graph, and the control structures of most programming languages can be straightforwardly modelled by finite-state automata. So one promising route to testing the wire-crossing problem would be to define a language which enforces the rule that the graph of the control structure must be planar.

This is the approach taken by Beturing, and the results from it strongly suggest that this part of the strong claim does not hold - that is, that it is possible to have a universal Turing machine whose control graph is strictly planar in nature. A sketch given by Minsky in Computation: Finite and Infinite Machines, of a Turing machine representation of a tag system, buttresses this idea: there is nothing complicated about the control structure whatsoever.

This is not an entirely surprising result when one considers structured programming. Forbidding arbitrary GOTOs is very similar to forbidding a non-planar control graph. Yet structured programming languages are clearly no less powerful than Turing machines.

However, Beturing does not represent a complete test. Anything more complex than an FSA has an extra component, namely storage shared by all the states. If access to this storage from any state requires some sort of non-planar connection, then the language might be non-planar even if the control graph is. For example,

  1
 /|\
2 3 4  M
 \|/
  5

In the above graph, there will always be one state (2, 3, or 4) that cannot access M without drawing a line that crosses one of the existing lines.

The Braktif cellular automaton, inspired by Archway (which was an attempt at a proof similar to Beturing, but based on Brainfuck instead of a Turing machine,) represents a slightly more refined test. However, it is largely intuitive and still incomplete - it has not been shown that Braktif's transition graph is strictly planar. In fact, it is now suspected that any multidirectional cellular automaton needs a state diagram with crossing edges.

For any language

The question remains, even if the wire-crossing problem is shown one way or the other in a particular language, whether or not that result carries over to every other language in the same computational class.

There might be some systems where, due to the operations and/or semantics, the strong claim effectively holds. Examples that come to mind include:

• Boolean circuits, where it is not known if it is possible to construct a planar storage device (i.e. a flip-flop) besides an RS latch, or whether RS latches are sufficient for storage. Circute respresents such a system as an esoteric programming language.
• Wierd, where the direction of a wire and the semantics are intimately linked, and where substantial controversy exists regarding wire-crossing.

Weak claim

The weak claim for the wire-crossing problem is that some algorithms will be less efficient if restricted to planar graphs. This is almost certainly true. A Kolmogorov machine, for example, which uses (a special kind of) an arbitrary graph instead of the linear tape found on a Turing machine, can be demonstrated to provide more efficient implementations of algorithms. This intuitively makes sense; where the Turing machine must traverse several tape squares to get to an arbitrary square, the Kolmogorov machine need only follow one of the many edges extending from the current vertex.