Talk:Wire-crossing problem

Conway's Game of Life has been shown to be Turing-complete: http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life.

Can we not describe every GoL program as a planar graph by definition, thinking of each cell as connected to its 8 neighbors?

No wait, my bad. The grid is in a plane - but the graph (at least sufficiently large) is nonplanar when you think of all those crossing diagonals.

Submitting this discussion as a testament to my own impulsiveness.

--jhw 19:23, 20 Dec 2006 (GMT)

Aha.

There are other elementary cellular automata which are trivially planar. See Rule 110 under http://en.wikipedia.org/wiki/Elementary_cellular_automaton. I believe this scuppers the Strong Hypothesis for the Wire-Crossing Problem: Rule 110 can solve all languages solved by any other Turing Machine can solve, and yet Rule 110 forbids the construction of programs which are non-planar graphs.

Or is there something about cellular automata which violates the (admittedly vague) assumptions in the Wire-Crossing Problem?

--jhw 19:36, 20 Dec 2006 (GMT)

Consider this: http://www.kongregate.com/games/PleasingFungus/manufactoria

in this 'planar' language its posible to implement BCT WITHOUT brigding. and as bct is Turing complete the strong claim is thus proofen to be wrong. Stfu&thnk 15:59, 18 December 2010 (UTC)

Possible proof of planarity turing completeness?

I might be missing something here, but I feel it should be pretty easy to show any non-planar Turing machine can be represented by a planar one. Suppose we have a non-planar Turing machine M, and we embed it in the plane such that any time we have an intersection of edges, we only have two edges cross at that point. At each such intersection, add in a new state for that intersection. We also add two values to our tape alphabet. When we follow a transition into such an intersection state, we record which state we came from. Let's call the source states L and R. Then once we get to the intersection state, we check whether we wrote the symbol indicating we came from state L or state R, and move along the corresponding output transition. Thus we just add basically a 'bridge' state that keeps track of where we came from, which limits where we can go to. Then there should be a couple minor details on implementation. Additionally, if we have more than two edges intersect, we simply switch from an L state and an R state to more than two input states. --(this comment by 174.109.246.19 at 02:49, 14 July 2015‎ UTC; please sign your comments with ~~~~)

Boolean circuits?

Can anyone give any insight on why the text claims that "it is not known if it is possible to construct a planar storage device (i.e. a flip-flop) besides an RS latch"? It sounds strange to me, given that it's possible to cross signals without crossing wires, see [1]. -pgimeno (talk) 17:20, 22 December 2018 (UTC)

Probably simply that the author didn't know about it. You can do an "XOR swap" a^=b; b^=a; a^=b with no wire crossings (and even if you go down to NAND gates, you can implement an XOR with NAND gates with no crossings of data wires). So the wire-crossing problem isn't interesting in the digital logic setting. (Actually, the wire-crossing problem seems to be uninteresting in most settings, which could be why people tend not to care much about it nowadays.)

Things get rather more complex when you take the power supply into account; if you're trying to prevent that crossing the data wires too, that means you need to produce a planar swapping device that can take its power entirely from the signals on the wires. I'm not sure whether that's possible; after all, you can't implement most logic gates like that (e.g. 1 XOR 1 = 0, meaning that an unpowered XOR gate would have to construct a path to ground but wouldn't have a negative power supply to do so). It might be possible using 1 (connected to positive supply) and Z (disconnected) as the logic levels, but you'd suffer from the voltage dropping every time you had to cross wires, meaning that the circuit would likely need a very high-voltage power supply and buffers all over the place. --ais523 12:15, 23 December 2018 (UTC)