The Physical Theory of Computation

[rocketdodger]

In some threads in the religion and philosphy section, people have mentioned that the computational model of consciousness can't currently account for all we know because there is no "physical" theory of computation.

The main argument used by these individuals is that consciousness can't be explained by computation because "there is nothing going on in a physical system in which computation is taking place that isn't also going on in a physical system in which computation is not taking place." Leaving aside the problems with "physical," such as "what does that even mean," let's just humor them and see what we can come up with.

Here is what I have gotten so far:

"Computation," in a physical sense, can be reduced to categorizing input, or mathematically speaking partitioning sets.

This is easy to express in physical terms. Suppose there is a system S, with possible inputs (which are just the state of the external world) W = {w1, w2, ... }. If S computes it will partition the set of all possible external states according to some criteria, into at least two non-empty and non-equal subsets. For example, it might partition {w1, w2, ...} into {w1} and {w2, ...}.

To partition (or categorize) all a system has to do is react according to a non-invertible function. That is, at least two distinct inputs need to map to the same internal state (or output).

Now -- this is important -- a common error these people regurgitate is that "anything can compute, because you can just arbitrarily set a threshold in the output of any function and partition accordingly." For example, a rock heating up in the sun can compute because it constantly changes temperature, etc. WRONG. In this case, it is not the rock that is doing the partioning, it is whatever is observing the rock temperature that is doing the partioning. In other words, the computation has just been bucked off to someone else. Up until the rock changes physical state -- by melting, or cracking, whatever -- there is no categorization occuring. If the rock melts, or cracks, then certainly there was a categorization -- all temperatures lower than the current rock temperature have been partitioned from all temperatures above. But a normal rock sitting in the sun is not computing.

This physical definition of computation also works nicely with the concept of "switching," another favorite topic of certain individuals. Switching is a type of categorization. Let S be a switch whose internal state changes in a non-invertible way according to the external variable V. It is trivial to show that S partitions external state into {V} and {w1, w2, ...}. That is, a switch categorizes the world into things that turn it on or off and things that do not.

If anyone sees errors in my logic, or has other notions they would like to share, please speak up. I am quite sick and tired of this "lack of a physical theory" being used as a smokescreen in discussions.

[sol invictus]

Perhaps one can define computation as a process in which the entropy of some subsystem decreases? I'm not sure that's a good definition, but it sounds equivalent to your idea of partitioning input and might be easier to work with.

[roger]

You are kind of asking us to redo all of information theory :)

I'm having a bit of trouble parsing your post, in that the position of "these people" isn't quite recognizable to me. But let's not worry about that.

I think you are confusing equivalence with identity. If I compute 2+2=4, that does not mean 4 apples appear on my desk. It is an equivalence. I have proven that if I take 2 apples, and then 2 more, I will have 4, and I have proven that act is computable. It is not an identity, because if I do the computation on a computer, I don't have 4 apples. Assuming IS claims that is just so wrong.

So, as to your rock, the claim is not that the rock's temperature is being "computed" just like a PC. The claim is that it is computable. Equivalence, not identity. In a bit more detail, the rock is in a state - broadly speaking, the molecules are all vibrating around at some speed, and this is entirely independent of any observer. It has nothing to do with categorization - the rock doesn't 'know' its at 233 Kelvin, any more than the computer 'knows' that memory location 4EA2943F is set to 3FFE, and that that happens to represent what the current energy input to the rock is from the sun. It's just a state.

The next sticking point will probably be model vs "reality". Just stick the computer in a robot with sensors, and have it go do it's thing - it'll all be real. Consciousness is physical and computable proponents, such as myself, state exactly the same kinds of things happen in the robot as a human - a physical substrate (wet brain in one case, silicon in the other) process information and perform actions on the "real world". If the silicon brain has a symbol for a 'tree', so does the wet brain. Everything they do is the same (since we are positing the silicon brain is a particle by particle simulation of the wet brain). Hence, unless there is something 'extra' in a wet brain that has never been discovered, that robot brain must be equally conscious as the wet brain.

[roger]

Perhaps one can define computation as a process in which the entropy of some subsystem decreases? I'm not sure that's a good definition, but it sounds equivalent to your idea of partitioning input and might be easier to work with.Sol, if this topic interests you, hop on over to the Robot Consciousness thread and give me a hand. We have people claiming things like chemistry is not computable - that it's too "fluid", etc. I'm attacking that from the information theory front, but it'd be nice to have a physicist point out that chemistry is just QM on a macro level, and completely computable (or, if I'm wrong on that point, spank me).

[roger]

rocket, the Church-Turing thesis states that computable functions are those that can be computed with unlimited memory and time with a mechanical device. This means (with math not shown here, see the thesis) that any algorithm is computable. Hence, if your rock's temperature can be expressed as an algorithm, it is computable.

[rocketdodger]

Perhaps one can define computation as a process in which the entropy of some subsystem decreases? I'm not sure that's a good definition, but it sounds equivalent to your idea of partitioning input and might be easier to work with.

Hmmm.. I wonder if the two really are equivalent? That is a good exercise for me to work on today in my spare time... if so, that would be really neat.

[rocketdodger]

I'm having a bit of trouble parsing your post, in that the position of "these people" isn't quite recognizable to me. But let's not worry about that.

Well, actually, everything you have past this point doesn't really have anything to do with the issue, lol.

The argument in question all started when PixyMisa suggested that "switching" is what allows brains and computers to do what they do -- and in general, for computation to occur. Westprog demanded a "physical" definition of switching, and every definition we provided resulted in the same response -- "that process also occurs in a rock sitting in the sun."

So the OP is about what, exactly, happens in a physical system that is computing that is not happening in a physical system that is not computing. In other words, we are interested in a very simple "physical" definition for a process that we can use to point at a group of molecules and say "there, that system is computing" while pointing at another group and say "there, that system is NOT."

Whether or not the systems themselves are "computable" is an interesting question but has nothing to do with what I am talking about here.

[roger]

rocketdodger, google recursion theory. This is a good intro article:
http://www.answers.com/topic/recursion-theory

I sincerely advice you not to try to redefine computability. You will either discard decades of work and render conversation with you impossible, or you will do a lot of work to just end up with the same definition used in the recursion theory field.

[The Man]

Perhaps "switching" controlling "switching" is the actually physical aspect of computation. I can turn on a light with a switch but I don’t think that would constitute computation. If the light were turned on by a combination of switches each affecting the output of another in some way that I think would then be some form of computation.

[roger]

Well, actually, everything you have past this point doesn't really have anything to do with the issue, lol.

The argument in question all started when PixyMisa suggested that "switching" is what allows brains and computers to do what they do -- and in general, for computation to occur. Westprog demanded a "physical" definition of switching, and every definition we provided resulted in the same response -- "that process also occurs in a rock sitting in the sun."

So the OP is about what, exactly, happens in a physical system that is computing that is not happening in a physical system that is not computing. In other words, we are interested in a very simple "physical" definition for a process that we can use to point at a group of molecules and say "there, that system is computing" while pointing at another group and say "there, that system is NOT."

Whether or not the systems themselves are "computable" is an interesting question but has nothing to do with what I am talking about here.But computable is the issue, isn't it? It just so happens that the silicon substrate uses switching; that does not mean that computation is switching. I cook on a gas stove - that does not mean you can't cook with electric, a solar oven, etc.

So, I don't even know what you mean by an object that is not "computing". You claim some things are computing, others aren't, but don't have a precise definition of 'computing'?

I think you have it backwards, so far as information theory goes. We have computability theory, where computability is defined in several ways (Turing, Lambda, etc). The computation is just carrying out that in whatever way. You can have a lambda expression for 2+3. The computation is getting 5. It doesn't matter if you slap 2, then 3 apples on a counter, run the calculation through some NAND gates, or do it with pencil from the standpoint of how the word computation is used in information theory.

As far as I am concerned, the temperature of a rock is computable. I'm not quite sure why it is important whether or not that rock is using "switching" to reach that temperature to your discussions.

A big problem in understanding this for me is all the scare quotes: "switching", "physical", etc.

[roger]

I relooked at your OP - I'm still having trouble understanding what you want, and that is probably my fault. In any case, you are talking about sets. Set and state models is a form of defining computation. But, we can do it other ways, such as functional with the lambda calculus. Turing allows us to reduce one to another (excluding hypercomputation, which doesn't appear to be physically realizable).

I don't know if that helps you or not. In any case, I wouldn't get caught up with "switching" since we can define an equivelent model that doesn't involve switching.

[The Man]

Perhaps “switching” is not the best descriptive term although it is a common property of both computers and brains. Dependent outputs might be a more general description of the physical aspect required for computation as in a combination of positive and negative inputs resulting in some output.

[rocketdodger]

Perhaps "switching" controlling "switching" is the actually physical aspect of computation. I can turn on a light with a switch but I don’t think that would constitute computation. If the light were turned on by a combination of switches each affecting the output of another in some way that I think would then be some form of computation.

That is fine, but the issue remains, since westprog claimed a rock sitting in the sun was switching.

[rocketdodger]

But computable is the issue, isn't it? It just so happens that the silicon substrate uses switching; that does not mean that computation is switching. I cook on a gas stove - that does not mean you can't cook with electric, a solar oven, etc.

So, I don't even know what you mean by an object that is not "computing". You claim some things are computing, others aren't, but don't have a precise definition of 'computing'?

I think you have it backwards, so far as information theory goes. We have computability theory, where computability is defined in several ways (Turing, Lambda, etc). The computation is just carrying out that in whatever way. You can have a lambda expression for 2+3. The computation is getting 5. It doesn't matter if you slap 2, then 3 apples on a counter, run the calculation through some NAND gates, or do it with pencil from the standpoint of how the word computation is used in information theory.

As far as I am concerned, the temperature of a rock is computable. I'm not quite sure why it is important whether or not that rock is using "switching" to reach that temperature to your discussions.

A big problem in understanding this for me is all the scare quotes: "switching", "physical", etc.

You are still talking about computation theory on a higher level.

I am talking about how to implement computation at a physical level, the lowest possible level. Given a bunch of particles, how do you implement addition? Subtraction? Any type of computation?

[rocketdodger]

I relooked at your OP - I'm still having trouble understanding what you want, and that is probably my fault. In any case, you are talking about sets. Set and state models is a form of defining computation. But, we can do it other ways, such as functional with the lambda calculus. Turing allows us to reduce one to another (excluding hypercomputation, which doesn't appear to be physically realizable).

I don't know if that helps you or not. In any case, I wouldn't get caught up with "switching" since we can define an equivelent model that doesn't involve switching.

But you can't define an equivalent model that doesn't involve categorization, and that is just an isomorphism of switching.

Or if you can, please tell me. That is what I am after here -- is categorization at the heart of physical implementations of computation? Or Sol's "decreasing entropy?" Or are they both equivalent, and perhaps equivalent to something else as well?

[roger]

But you can't define an equivalent model that doesn't involve categorization, and that is just an isomorphism of switching.

Or if you can, please tell me. That is what I am after here -- is categorization at the heart of physical implementations of computation? Or Sol's "decreasing entropy?" Or are they both equivalent, and perhaps equivalent to something else as well?
I don't know what you mean by these terms. I can guess, of course, but I can't be sure.

What a Turing Machine (TM) does is one form of computation. (computation defined by the act, not vice versa).

A TM is a simple machine - a paper tape, a writer that can write 1/0 on the tape, a reader that can read 1/0 from the tape, a motor that moves the tape one position, and a very simple set of instructions - move forward, move back, write 1, write 0, and a conditional or two: if read is 1, then advance and write 0.

What the TM does is defined as computation.

Is that "categorization" or "switching" as you mean it? I don't know. But it is one definition of computation that is extremely widely used.

There are other models, such as lambda calculus, that don't use the TM definition, though it can be converted to TM, and vice versa, with no loss.

Note that what TM does sounds very unlike a rock heating the sun. What lambda calculus does sounds exactly like a rock heating in the sun. So I'd be wary at looking for physical correlates, and making exclusions (the rock does or doesn't compute) based on any specific definition of computation.

Entropy in information science usually refers to Shannon entropy, which is a measure of how much information is in a message. I wouldn't really use it to define computation, though I am not claiming it cannot (I honestly don't know).

You can say a boson computes, because it obeys Bose-Einstein statistics. Not a general purpose computer, of course, but they are computations. Elementary particles are as low level as you can get.

[drkitten]

But you can't define an equivalent model that doesn't involve categorization, and that is just an isomorphism of switching.

Or if you can, please tell me. That is what I am after here -- is categorization at the heart of physical implementations of computation? Or Sol's "decreasing entropy?"

No, and no.

For a proof, see a Moore machine (http://en.wikipedia.org/wiki/Moore_machine), which is a variation of a Turing machine (actually, an FSA) that generates output. The idea behind a Moore machine is simply that it transforms an input string into an output string, but nothing about it requires that information be lost and it's very easy to write Moore machines that do not lose information.

Similarly, a simple TM program that reads an input and writes the input in reverse is performing "computation" but not losing information (and is also doing something that cannot be done by a Moore machine). In fact, there's a substantial research area in "reversible computing" (http://en.wikipedia.org/wiki/Reversible_computing) that studies this kind of non-irreversible transformations because, in theory, they can be made much more energy-efficient. If you chase this line of reasoning far enough, you end up with laptop computers with arbitrarily ong battery lives,.... which I definitely want and am happy for the NSF to try to invent.

[rocketdodger]

What the TM does is defined as computation.

Yes, yes, yes, but the question is what does a turing machine do, at a fundamental level, that a system of particles that is not TM equivalent does not do?

Obviously, the high level answer is trivial -- it computes. But that doesn't say anything about, for instance, the behavior of each particle in the system, and that is what I am after.

Note that what TM does sounds very unlike a rock heating the sun. What lambda calculus does sounds exactly like a rock heating in the sun.

How so?

You can say a boson computes, because it obeys Bose-Einstein statistics. Not a general purpose computer, of course, but they are computations. Elementary particles are as low level as you can get.

Isn't that a bit like the rock in the sun?

It seems to me that this is just interpreting statistical results in such a way that they could be used as computation, not actual computation in and of itself.

Maybe computation is the wrong word for what I am after.

To be clear, what I am after is a behavior that allows certain systems of particles to do useful things, where "useful" is best defined in some sort of Darwinian sense.

[rocketdodger]

No, and no.

For a proof, see a Moore machine (http://en.wikipedia.org/wiki/Moore_machine), which is a variation of a Turing machine (actually, an FSA) that generates output. The idea behind a Moore machine is simply that it transforms an input string into an output string, but nothing about it requires that information be lost and it's very easy to write Moore machines that do not lose information.

Similarly, a simple TM program that reads an input and writes the input in reverse is performing "computation" but not losing information (and is also doing something that cannot be done by a Moore machine). In fact, there's a substantial research area in "reversible computing" (http://en.wikipedia.org/wiki/Reversible_computing) that studies this kind of non-irreversible transformations because, in theory, they can be made much more energy-efficient. If you chase this line of reasoning far enough, you end up with laptop computers with arbitrarily ong battery lives,.... which I definitely want and am happy for the NSF to try to invent.

I don't see any possible way to implement any of those without relying on some type of component that categorizes.

At the very least, every TM must have a component that can distinguish it's tape from the rest of the world, and each character of the input string from other possible characters, right? Isn't that fundamentally categorization?

[drkitten]

At the very least, every TM must have a component that can distinguish it's tape from the rest of the world, and each character of the input string from other possible characters, right? Isn't that fundamentally categorization?

Only in the sense that the rock's ability to distinguish the photons that hit it from the rest of the photons in the world is also categorization.

Ergo, a rock computes. I don't think you want to go that way.

[drkitten]

Yes, yes, yes, but the question is what does a turing machine do, at a fundamental level, that a system of particles that is not TM equivalent does not do?

Ah. Phrased like that, the answer is obvious. "Nothing."

A TM is not equivalent to a push down automaton or to a finite state automaton.

A push down automaton is not equivalent to a finite state automaton.

However, a PDA is equivalent to an FSA with an attached stack.

And a Turing machine is equivalent to a PDA with an attached stack, or an FSA with two stacks.

So unless you can tell at a particulate level whether this particular particle is part of a stack and whether that stack structure is replicated elsewhere in the system, you can't tell whether or not a set of particles is TM-equivalent.

Perhaps it can be done, but we don't have the technology and terminology for it, just as we can't explain why football teams punt on fourth down and not third in terms of QM. Either way, the question is asked at the wrong level.

[rocketdodger]

Only in the sense that the rock's ability to distinguish the photons that hit it from the rest of the photons in the world is also categorization.

Ergo, a rock computes. I don't think you want to go that way.

Well, not really.

The rock isn't actually doing the categorization since it has no say whatsoever about the members of each set.

Contrast that with the turing machine, which could accept or reject anything it wanted as tape depending on how it was set up.

Now, it does seem that a rock could categorize all particles into photons and not-photons, but even that is a stretch since it is not clear that the response of the rock to a photon is non-invertible.

[rocketdodger]

Ah. Phrased like that, the answer is obvious. "Nothing."

A TM is not equivalent to a push down automaton or to a finite state automaton.

A push down automaton is not equivalent to a finite state automaton.

However, a PDA is equivalent to an FSA with an attached stack.

And a Turing machine is equivalent to a PDA with an attached stack, or an FSA with two stacks.

So unless you can tell at a particulate level whether this particular particle is part of a stack and whether that stack structure is replicated elsewhere in the system, you can't tell whether or not a set of particles is TM-equivalent.

Perhaps it can be done, but we don't have the technology and terminology for it, just as we can't explain why football teams punt on fourth down and not third in terms of QM. Either way, the question is asked at the wrong level.

That isn't really what I meant.

What I meant was, if you were given a system of particles, what behavior would be absolutely necessary for you to be able to build a turing machine with the system?

[Reality Check]

A Turing machine (http://en.wikipedia.org/wiki/Turing_machine) is an abstract concept and cannot be built from a system of particles.

[Piggy]

Sol, if this topic interests you, hop on over to the Robot Consciousness thread and give me a hand. We have people claiming things like chemistry is not computable - that it's too "fluid", etc. I'm attacking that from the information theory front, but it'd be nice to have a physicist point out that chemistry is just QM on a macro level, and completely computable (or, if I'm wrong on that point, spank me).

Lurking here to learn, but no, if you mean me, I'm not claiming chemistry is not computable.

Carry on.

[sol invictus]

That isn't really what I meant.

What I meant was, if you were given a system of particles, what behavior would be absolutely necessary for you to be able to build a turing machine with the system?

I'm pretty sure the answer is as I said at the top: your system of particles would have to be out of equilibrium, because only then would it be possible to lower the entropy of a subsystem.

[rocketdodger]

I'm pretty sure the answer is as I said at the top: your system of particles would have to be out of equilibrium, because only then would it be possible to lower the entropy of a subsystem.

Accepting for the time being that you are correct, and the two are equivalent (I need to brush up on thermo before I attempt a formal proof, so I probably won't do it any time soon lol), does it give us what we want?

That is, we know first that the entropy of the top level system -- the universe -- is always increasing. We also know the entropy of some subsystems of the top level are decreasing, for whatever reason. Will it turn out that any time a system does something to decrease the entropy of a subsystem, it makes intuitive sense (to us) to call it "computation?"

Off the top of my head I am leaning towards "yes," but I am not an expert at finding loopholes like some of these dualists are.

[blutoski]

Perhaps one can define computation as a process in which the entropy of some subsystem decreases? I'm not sure that's a good definition, but it sounds equivalent to your idea of partitioning input and might be easier to work with.

I was thinking about this overnight, and it seems to me that a random number generator may not fit this description, if you consider generating a random number to be 'computing'. (Would the input be the seed?)

[drkitten]

That is, we know first that the entropy of the top level system -- the universe -- is always increasing. We also know the entropy of some subsystems of the top level are decreasing, for whatever reason. Will it turn out that any time a system does something to decrease the entropy of a subsystem, it makes intuitive sense (to us) to call it "computation?"

I don't consider that it makes intuitive sense to call what my icemaker does "computation," but "decrease the entropy of a subsystem" is a pretty good description of what it does. Ditto for my air conditioner, or indeed for the person who vacuums up the can of freeze-dried coffee I spilled this morning on my office floor.

I would suggest, then, that the answer to your question is "no."

[rocketdodger]

I don't consider that it makes intuitive sense to call what my icemaker does "computation," but "decrease the entropy of a subsystem" is a pretty good description of what it does. Ditto for my air conditioner, or indeed for the person who vacuums up the can of freeze-dried coffee I spilled this morning on my office floor.

I would suggest, then, that the answer to your question is "no."

Hmmm...

... my initial reaction was to agree with you, but now that I think about it, why shouldn't what those things do be considered "computation?"

Because you could make a turing machine out of ice makers, or air conditioners, or janitors, or any other such device, if you were clever, right?

Or am I making a fallacy of composition here?

[drkitten]

Hmmm...

... my initial reaction was to agree with you, but now that I think about it, why shouldn't what those things do be considered "computation?"

Because you could make a turing machine out of ice makers, or air conditioners, or janitors, or any other such device, if you were clever, right?

Or am I making a fallacy of composition here?

Yes, you are. You can also make a Turing machine out of pipes and valves, or out of clockwork. That doesn't mean that pipes or gear themselves compute. Indeed, I think I could make a Turing machine out of anything that responds non-linearly. What makes it a Turing machine is the configuration, not the components.

But beyond that,.... you specified that we were looking at whether `it makes intuitive sense (to us) to call it "computation"' If you want to redefine "computation" to include ice-makers and janitors, it not longer fits our intuitions. (It also no longer fits eighty years of mathematical theory that we have to throw out, but we can put that to the side for the moment.) Is there an advantage to re-defining "computing" in this way?

[rocketdodger]

Yes, you are.

Alright, then lets change the topic to "what type of physical behaviors are needed for computation to occur."

Indeed, I think I could make a Turing machine out of anything that responds non-linearly.

Is that equivalent to decreasing entropy of a subsystem?

I am thinking it might be, because if you apply an entropy increase or decrease to a system, for it to do anything nonlinearly in response entails that system decreasing entropy somewhere one way or another. Right?

But beyond that,.... you specified that we were looking at whether `it makes intuitive sense (to us) to call it "computation"' If you want to redefine "computation" to include ice-makers and janitors, it not longer fits our intuitions. (It also no longer fits eighty years of mathematical theory that we have to throw out, but we can put that to the side for the moment.) Is there an advantage to re-defining "computing" in this way?

Nope, and I don't want to do that.

So decreasing the entropy of a subsystem -- and/or nonlinear behavior, depending -- is not computation, but might be a prerequisite for computation, and at least that has gotten me somewhere because I might be able to point to a bowl of soup and say "that soup is surely not computing because it doesn't even feature the physical prerequisites of computation."

[drkitten]

Is that equivalent to decreasing entropy of a subsystem?

No. Many non-linear functions are nevertheless reversible, which makes them entropy-preserving. And, in fact, the whole theory of reversible computation is about designing systems that perform computation in an entropy-neutral framework. (Perhaps obviously, I should also say that all subsystems of such a computer must themselves be reversible since if any part of the system destroys information, there is no way to recover it.)

So we have systems (reversible computers) that compute, but do not decrease entropy.

We also have systems (icemakers and janitors) that decrease entropy, but do not compute.

So they appear to be independent traits.

[sol invictus]

That is, we know first that the entropy of the top level system -- the universe -- is always increasing. We also know the entropy of some subsystems of the top level are decreasing, for whatever reason. Will it turn out that any time a system does something to decrease the entropy of a subsystem, it makes intuitive sense (to us) to call it "computation?"

It's probably too general. For example life fits this definition (in fact I've proposed it as the best general definition of that too). But presumably we want to distinguish between life and computation.

I was thinking about this overnight, and it seems to me that a random number generator may not fit this description, if you consider generating a random number to be 'computing'. (Would the input be the seed?)

You'd have to consider the whole process carefully. But anyway, I'm not sure that should be considered a computation.

I don't consider that it makes intuitive sense to call what my icemaker does "computation," but "decrease the entropy of a subsystem" is a pretty good description of what it does.

You probably could use your icemaker as a computer. But I agree the definition is probably too general - I'm just not sure how to sharpen it in a way that preserves its utility.

The reason I proposed it is that it coincides reasonably well with rocketdodger's first attempt at a definition. Decreasing entropy means you've sorted something into a more organized form. You've actually decreased the information in it, but - at least in the cases we would agree are real omputations - you've increased its utility by making it more accessible.

[sol invictus]

So we have systems (reversible computers) that compute, but do not decrease entropy.

Do you have an example of that?

[sol invictus]

Let's take an example: sorting a list of names into alphabetical order. Is it possible to do so reversibly?

I'd say no, because no matter what order the names started in, they always end up in alphabetical order. Hence the map is not 1-1, and the entropy changes as information gets erased. Clearly some steps in that process can be reversible - like translating the names from Roman characters into ascii - and you'd want to make as much use of such steps as you can to minimize energy costs.

But the fundamental algorithm is irreversible, and it seems to me that such processes are the essence of computation (but I admit to near-total ignorance of computer science, so I might be completely wrong).

[drkitten]

Do you have an example of that?

Physical examples? No. We can't actually build systems with no parasitic losses, any more than we can build completely leak-proof pipes. (That doesn't bother me as much as it might when we're talking about Turing machines, you know?) But the field of "reversible computing" is well-known and there are many examples of designed computers that are provably Turing-equivalent. I'm sure your Google-fu is up to it.

[sol invictus]

But the field of "reversible computing" is well-known and there are many examples of designed computers that are provably Turing-equivalent. I'm sure your Google-fu is up to it.

Can they perform operations like sorting lists?

[drkitten]

Let's take an example: sorting a list of names into alphabetical order. Is it possible to do so reversibly?

Yes.


I'd say no, because no matter what order the names started in, they always end up in alphabetical order. Hence the map is not 1-1, and the entropy changes as information gets erased.

You simply preserve the additional information. The output of a reversible algorithm to sort a list of names would be a list of names, plus an apparently random collection of other bits that indicate what the actual permuation used to do the sorting was. Then, when you feed the list and the permutation ID backwards into the computer, you get your original list back.

What actually costs energy/entropy is the act of throwing information away (or in more typical terms, writing a bit instead of toggling it). If you never throw any information away, you lose nothing in computation.

It's kind of cute, and mathematically elegant, and so far completely useless. Of course, they used to say that about number theory too, and now Ron Rivest is a zillionaire,....

[drkitten]

Can they perform operations like sorting lists?

No. They're provably Turing-equivalent, but they can't sort lists. Funny how that works, you know?

See my previous post for a more detailed and less sarcastic answer.

[sol invictus]

You simply preserve the additional information. The output of a reversible algorithm to sort a list of names would be a list of names, plus an apparently random collection of other bits that indicate what the actual permuation used to do the sorting was. Then, when you feed the list and the permutation ID backwards into the computer, you get your original list back.

I don't see how that provides a counterexample to my proposal. The list itself is the subsystem, and its entropy decreased when you sorted it.

As for efficiency gains - where did you get the additional memory space to preserve that extra information? If you got it by erasing a register, you paid the same cost you'd have paid if you simply didn't keep it at all (i.e. if you did a normal irreversible computation). If you happened to have a previously formatted register sitting around, fine - you increased its entropy by precisely the amount you decreased that of the list (if you leave in a perfect dissipation free world, that is). But I don't see how that's even a potentially practical solution to computers generating heat - where do you get the formatted registers from?

[69dodge]

"Computation," in a physical sense, can be reduced to categorizing input, or mathematically speaking partitioning sets. [...] To partition (or categorize) all a system has to do is react according to a non-invertible function. That is, at least two distinct inputs need to map to the same internal state (or output).

Are you saying, for example, that adding 1 to a number, or doubling it, are not computations, because we can always get back the original number by subtracting 1 from the result, or halving it?

[rocketdodger]

Are you saying, for example, that adding 1 to a number, or doubling it, are not computations, because we can always get back the original number by subtracting 1 from the result, or halving it?

No, I am saying that I can't think of a way to actually implement addition in a physical system without a non-invertible behavior.