Puzzle for the Day

Hmmm ... the set {AND,OR,NOT} is of course universal ... gate array programmers know that {NAND} is universal by itself ... so is {NOR} by itself ... this makes it evident that the tough part of fire-based programming is implementing any one of {NOT,NOR,NAND} using the medium of fire.

In the physical world, how does one use fire to stop fire? Easy ... by setting a backfire ... thus your gates might need to include an internal flammable fuse that (1) is hard to ignite (needing two fire inputs), and (2) the fuse is an internal wire of the gate ... then run your circuit off a two-stage clock (set internal fuses, then fire the gate), and you're done!

In addition to using backfires, you can also control the oxygen supply using fire. If the oxygen has been consumed by a fire, then there will be none available. Of course, this is a bit more involved than simply laying out some strings and lighting them in appropriate places, but depending on the fuel used it may be more reusable.

So it appears that Michael is proposing a variant of Schroedinger's Computer.

At the fiber-optical level, we can imagine a 1x1 coupler, consisting of a Fabry-Perot cavity having a nonlinear refractive index, such that the coupler is transmissive for power levels that are even multiples of unity, and reflective for odd multiples of unity.

AFAICT, this (nonlinear) coupler, plus orthodox linear 2x2 couplers, plus a phase delay coupler, is a universal set of components for computation not with fire, but with light.

Real-world optical computers need occasional power amplifiers too, which are subject to Carlton Caves' 2 dB standard quantum noise limit for phase-sensitive amplification. And in fact, amplifiers that approach Caves' limit quite closely are off-the-shelf items in the telecommunications industry.

I know all this because the above device is just a time-reversed version of the interferometric sensors that are standard practice in quantum spin microscopy.

Does this mean that sensing processes can be viewed as computation processes?

Yah, sure, you betcha!

If 0=no fire and 1=fire then how do you do a simple NOT gate? That means given no fire you have to output fire. Spontaneous combustion?

Ditto for NAND, NOR, and XNOR that output 1 when inputs are 0.

I don't see how you can make a fire computer work with the given definition of 0 and 1.

There is in fact a whole field of thermal computation: They call it "phononics".

http://physicsworld.com/cws/article/print/33123

I think it's possible:
OR is as you say >-

AND is extremely tricky to draw in ascii. Essentially you make a fire block by placing a gap in each input. Then above the gap you place a piece of flammable material ( for clarity only one shown denoted by ===) suspended by a non flammable thread (&). When released this dangles perfectly in the gap. Then you hold this out of the gap with a flammable thread connected to the opposite input ( | ).

The idea is that when you light one input it burns until it reaches the gap, then stops. It also fills in the gap on the opposite side by igniting the flammable thread, which burns and drops the === material into the gap. However since the other input isn't lit it doesn't lead to an output.

If both inputs are lit then the fire burns both flammable threads dropping the flammable material into the gaps on both sides. When the fire from the input reaches that point it can cross the filled in gap i.e. you get an output iff both inputs are lit. [in the diagram i've only shown one crossing because it's already too complicated to be clear. I've marked where the second crossing would start with an @]

+--+
| |
| |
| |
| |
---+ +- ---\
| \
| \
+----| & >----------
| & /
@ === /
--+ +-- ---/
| |
| |
| |
| |
+---+

A not gate could be done along similar principles but would need a fire rail (marked at the start with @) such that if there's no fire we can start one. This time suspend a piece of flammable material (===) in the gap. If the input is burning it sets fire the the thread holding the piece in the gap such that it falls. when the real input gets there it can't get across. The fire rail needs to be slightly longer than the input and contact the input just before the gap. If the input causes the material to fall then, when the fire rail signal arrives at the gap they'll be nothing there (because the input will have already burnt the thread). If the input is zero then when the fire rail signal arrives the flammable material in the gap will still be in place and the signal will get across.

+----+
| |
| |
| |
| |
| |
| |
@--+ |
|
+---- ^ -----+
| | |
---+ +-+----===---
| |
| |
| |
| |
| |
| |
+--+

I think that this would be much more obvious with some real diagrams or, better yet, a working model.

Dan, interesting but the premise is the use of two temperatures to determine the digital value. Related, but not the same problem as fire and string.

Ok, I didn't realise that when you comment it removes any spaces from the start of the lines.

That's completely destroyed my, already fairly poor, attempts at ascii diagrams.

To summarise the now fairly useless comment above:

you can make an AND gate and a NOT gate by carefully either dropping or removing bits of flammable material into/from gaps dependent on the state of the inputs.

Colin, your objection applies equally to optical computers -- one solution is simple -- specify that at least some (ancilla) input bits that are initialized to "fire/light"!

A related real-world issue is fan-out -- in the optical world this is simply "amplifier followed by beam-splitter".

A final real-world issue is a beam-dump -- in the optical world these are ports at which vacuum fluctuations enter.

Marc: I added the pre html tag to the allowed tags and inserted them into your diagrams. Sorry about that.

I'm not sure that's made them much clearer.

I based my designs on some that I came up with to compute using dominos. It turns out other people have had the same idea and even taken it as far as placing a youtube video.

I think it's relatively easy to generalise from this to fire

Marc, that utube "domino logic" video is terrific!

Dave, this IMHO is a terrific post ... not only is it fun, but it encourages us to reflect upon past, present, and future computing technologies.

For that subset of readers who are techno-history geeks (a tribe that I belong to), I append a reference to a terrific 1991 article from IEEE Micro titled The drive to the year 2000.

Like the majority of technology-related articles written by experts that attempt to foresee the technological future ... this article gets pretty much everything right.

Faster logic, smaller feature size, more memory/gates ... definitely! The future of mass storage: first magnetic, optical a distant second, flash memory coming on strong. The future of displays: plasma and LCD screens acquiring color and getting cheaper (these predictions were right on).

Dark horse computational technologies of 1991: SQUID computing, optical computing, molecular computing, natural speech recognition and synthesis ... (also right-on, these technologies are still dark-horses today, two decades later).

Is there anything that this IEEE article did *not* get right? Well, the article performed poorly on applications: "computer-supported collaborative work ... greater use of email" ... these tepid insights are nothing like the explosion of the Internet that actually eventuated.

We can ask, what computational technologies are destined to "catch fire" in the sense of showing explosive growth in the next couple of decades? And (equally important) what new communities will be build upon these technologies?

Well, the same concepts that Dave's post challenges us to conceive (for fun) in the context of "fire-based" informatic technologies, also challenge us when we conceive (for purposes of in-depth systems engineering and strategic planning ... and for fun!) all other forms of informatic technologies.

My own analysis of our technological future predicts that the following technologies will "catch fire" (and are in fact, already catching fire): "conformational molecular biology", "quantum spin biomicroscopy", and "large-scale symplectic simulations".

Amazingly (to me anyway) the hot-as-fire phrase "conformational molecular biology" is not presently indexed anywhere on the WWW, Inspec, or PubMed ...

So remember, you read it first on "Quantum Pontiff". :)

--------

@article{Author = {Myers, Ware}, Journal = {IEEE Micro}, Number = {1}, Pages = {10 - 13, 68-74}, Title = {The drive to the year 2000}, Volume = {11}, Year = {1991}}

It shouldn't be too hard to make an AND gate. Tie the output string to the wick of a short candle and balance it over the two input strings. If both input strings are lit, the bottom of the candle melts evenly and the output string is lit when the wick drops. If only one input is lit, then the candle melts unevenly and falls to one side, leaving the output unlit.

As Colin notes, implementing NOT with the given definition of 1 and 0 isn't particularly nice. Instead, why not use two strings in parallel for each bit? The state {on fire, not on fire} can represent a 1 and {not on fire, on fire} a 0. Then you can easily make a NOT by swapping strings. An OR gate would be made by tying together the left-hand strings of each input and doing the candle trick with the right-hand strings. AND would be the exact opposite.

I suppose you'd have to make sure that the strings burnt at the same speed, but I think that's a plausible primitive computer...

You folks are fixated on making a universal digital computer. That's not what Dave asked for.

It's simple to build a computer out of fire.

For example.

Let's say I want to compute how long it will take to burn object X. To do this I follow this simple fire-based computational procedure.

1. Gibber at moon. Note its position in sky.
2. Light object X, which may or may not be a theoretical computer scientist, on fire.
3. Dance maniacally around object.
4. Jump over flaming object.
5. When object is fully burned, howl at moon. Note its position in sky.
6. Use diff in moon positions to compute time using (fire-based) look-up table.

Voila. Fire based analog computer.

By the way, Dave ... "conformational molecular biology" now shows up on Google's search engine ... less than two hours after it appeared on Quantum Pontiff for the very first time in the known web-verse.

Jeepers ... Google/Skynet must be indexing Quantum Pontiff several times a day! :)

Cyberdyne systems writes efficient code.

There are a couple of ways, but they aren't terribly elegant. I'm not sure it's possible to do with string and nots only, but you can at least use a dual rail encoding (as with linear optics) to allow easy not gates. I'm not sure you can do much more with an idealsied string and knot computer unless we allow some extra physics.

Can I use gravity? If so, it is relatively easy. OR gates are achieved as you explained. Basically the trick is to use one string to elevate another. If the supporting string burns, then the other string will drop (hanging vertically down from its next support. If we start another string there, then it will burn only if the second string is also burning, allowing an AND gate.

A NOT gate can also be achieved in this way. Basically you use the same setup with one string supported by another. The input in this case comes in on the supporting string. The supported string starts lit. A third string is used for output and is held just above above the intersection of the other two strings. Hence if the supporting string burns, the second string drops before it can light the output, but if not, then the output is ignited by the second string.

I realise that in these scenarios there is a danger of one input string igniting the other. This doesn't matter, however, since it will start burning at the midpoint, which can be positioned out of reach of the output string.

Another variation on this theme of using supporting strings is simply to suspend the system over water, so that when supporting strings are burned, they realease there supported string into water, but this is a more complicated model.

Also in the (fun!) general category of "simple, irreversible physical processes that are universal for computation" is this Turing Machine realized in Conway's Life.

Conway's Life is reducable to a Bacon Fire Machine under the mapping: alive â on fire; dead â not on fire; born â lit by neighboring fires; dies of loneliness â fire extinguished by heat loss; dies of crowding â fire extinguished by lack of oxygen.

Then this Life-Fire reduction implies: "Fire-based computers are universal and self-constructing".

Joe is right -- it is almost certainly not possible to do it with just string and fire. You need some additional element (as suggested by various people above).

It is easy to see this: the fire will eventually completely consume any connected component that has a part of it on fire. (The fire may disconnect the component, but each of the new sub-components will also be on fire.) The graph REACHABILITY problem is complete for the FIRE complexity class.