1. 16
  1. 6

    I wrote a paper with this definition of computation:

    the process by which the fact that one system is rule governed is used to make reliable inferences about another rule governed system.

    It follows that “being a computer” is not an objective fact but agent relative.

    1. 3

      Indeed. After all, computers used to be women.

    2. 4

      I think you give up on Turing machines too quickly. On the transition to LBAs, why not ask about Turing completeness? Your rock LBA cannot emulate any multi-state LBAs, at least not for any useful number of steps. - That said, I wouldn’t be so afraid to ground definitions in practicality. For instance, Rule 30 (Turing complete!) can famously be computed on a mollusk shell. Are mollusk shells computers? I’d say “Yes, but not very good ones.”

      I’d say it’s like the “definition of a heap.” A computer is a physical system that should be isomorphic to a LBA with easily controllable inputs, at least two states, lots of tape length, useful outputs, high performance, etc. Some of those can be missing; if too many are missing, it’s not a computer.

      LessWrong has a good Sequence about all this.

      1. 4

        A Turing machine which runs forever without repeating has infinitely many states. Any finite collection of particles has finitely many states. Thus, no finite collection of particles can implement a Turing machine which runs forever. Similarly, a Wang tiling which fills the plane aperiodically will also exhaust the finite states possible in a finite collection of particles.

        Can a collection of crabs be a computer?

        1. 2

          Can a collection of crabs be a computer?

          There’s a Rust joke in here somewhere.

      2. 3

        When I think of examples, my intuition is that a computer processes information for some purpose:



        • the San Fracisco Bay
        • a clothesline hanging from two points
        • a rock
        • a hammer
        • the weather

        A rock isn’t usually a computer, but if you use it to compute something (a ballistic trajectory?) then it can be.

        1. 2

          A rock isn’t usually a computer,

          I just remembered. Though to be fair in this case the computer isn’t just the rock (or the rocks), but the combination of the rocks and the bored immortal being that is placing them.

          1. 5

            There’s this tweet:

            if you ever code something that “feels like a hack but it works,” just remember that a CPU is literally a rock that we tricked into thinking


            Follow up tweet:

            not to oversimplify: first you have to flatten the rock and put lightning inside it

          2. 2

            Evolution blurs your attempt at a clean categorization. There are lithotrophic bacteria which inhabit rocks, and the state changes that they produce in their habitat are as purposeful as a ribosome transcribing RNA instructions.

            1. 2

              Even apart from organic state machines, there are probably lots of other natural state machines (orbiting bodies in the solar system). Indeed, everything in the universe seems stateful and thus part of some natural state machine or another, so which of these are computers? (Shakes fist at philosophy)

            2. 2

              ehhhhhh… I actually think there’s a distinction to be made there, because you can make lots of machines that calculate numbers that aren’t what we would now call a computer. So I think there’s a useful difference between “calculators” or “models”, which use physics do some math, and “computers”, which are Turing complete (ie, can repeat operations and make decisions).

              1. 1

                Those proteins that interpret DNA aren’t doing anything for some purpose, right? At least no more so than any other natural state machine.

              2. 3

                ”Attempting to run Doom on a rock would undoubtedly end in failure” <- I am waiting on the follow-up story that someone has indeed taken up the challenge of getting Doom to run on a rock

                1. 1

                  @Corbin might have an idea about what we might look for.

                  1. 1

                    This line triggered me as well.

                  2. 2

                    What’s the difference between a hammer and a rock? After all, people made hammers out of rocks for hundreds of thousands of years. There, same difference.

                    Less glibly, it’s 1) an artifact, that 2) can execute Turing-complete programs, and 3) hopefully produce some kind of output. I suppose if we want to get detailed, it does this without a human needing to do more than supply the program, input, and power.

                    1. 1

                      I feel like you’re close to a good insight which maybe you felt was too pedestrian to mention: “hammer” is a verb. Is water a hammer? No, but water can hammer. A stone and an iron hammerhead might have different crystalline structure, but they can both be used to hammer. Similarly, perhaps “computer” should be returned to its verb form, “to compute”.

                      1. 2

                        I’m not sure point you’re trying to make. Before we had machines for it, “computer” was a job that a human did. The first mechanical computers were exactly that: a machine where you turned a crank and it did the same operations a human computer would do. But that doesn’t change my classification at all.

                    2. 1

                      A rock doesn’t do computation when provided with energy. Now the question is, “what is computation”.

                      1. 1

                        Church turing thesis is the accepted answer. Energy of what form? Matter is energy.

                        1. 1

                          Almost exactly, except that matter != energy, but you can convert matter into energy. I’ll go a bit further though: the rock is not a computer, and nor are any of the basic components of a computer themselves a computer. Doping some silicon doesn’t give you a computer, but a way to direct one energy flow and in the case of transistors, based on another. What actually makes them a computer is their arrangement, and it’s that arrangement, mediated by the components, that does the computation by directing some form of energy in some manner.