4 ms·

> one can specify algorithms which require no thermodynamic work to implement Can you give an example? To my limited understanding, performing work without exp

> one can specify algorithms which require no thermodynamic work to implement Can you give an example? To my limited understanding, performing work without expending energy sounds like perpetual motion.

mjburgess 4y ago
Sure, this is the trap of thinking of computer science as either being about computers (machines) or about science. As mostly a kind of pure discrete mathematics, we need to be careful. Consider an algorithm which says: while(true) state *= +1, state *= -1, state *= +1, ... Now, identify the +1 state as the earth when in one-half of an orbit, and the -1 as the earth in the other half. And therefore the position of the earth as the logical bit ("the state") and its movement as the change to the logical bit. This is "perpetual motion", but the technical name in physics for this is inertial motion, and its common. Motion itself doesn't require work, using that motion for work, requires work. See also https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing
- sudosysgen 4y ago
  If you really want to be pedantic, even infinite inertial motion isn't possible, because a true vacuum is impossible, and there is thus necessarily drag somewhere. Also, I've said that before, but we already know that brains operate under an irreversible computation model.
  - User23 4y ago
    > Also, I've said that before, but we already know that brains operate under an irreversible computation model. We don't know that brains operate under any kind of computational model at all. It's often postulated, but it's not proved. Every attempt I've seen at a proof reduces to begging the question. Edit: To be clear I’m not saying a computational model of the brain can’t be a useful tool. Newtonian physics works quite well quite often even though reality isn’t Newtonian.
    - sudosysgen 4y ago
      To be clear, I'm not saying that everything the brain does can be modelled by a known computation model. All I'm saying is that the interesting part of what the brain does is computation, in that it takes in data, operates on it, and returns data. It does this in an irreversible manner because you cannot determine the input from the output (nor a significant part of it). If there is any model of how the brain works it will be a computational model. Perhaps a new one, and perhaps a radically different one, but it's still going to find the definition of a computational model.
      - User23 4y ago
        Ultimately, the open question here is this: are uncomputable functions just a mathematical fancy, or do there really exist processes that can only be fully correctly described by uncomputable functions? Personally I lean towards latter view. I’m the first to admit that I have no proof. It’s just my belief, because I find the metaphysical evidence compelling. I don’t object to investigating the former possibility, but I also don’t care for it just being baldly asserted. If the answer is affirmative, that means that science will probably never be solved and we’ll just have to content ourselves with incremental improvements in our understanding. That’s observably been the case up until now. Granted even if all processes are in fact described entirely by computable functions we might still never discover what they are. I hope it’s clear how all that relates to the concrete problem of understanding human cognition and the brain. I'm nowhere near smart enough to even begin to conceive of a mathematical framework for taming noncomputable functions in a pragmatic way, but I earnestly hope some genius comes along who is, supposing that noncomputable functions are needed to completely describe our reality.
        sudosysgen 4y ago
        Well, those functions are called uncomputable because, as far as we know, there is no repeatable way of computing them, right? So if the human brain was able to compute functions that Turing machines can't, it doesn't mean those functions are uncomputable, it just means the Church-Turing hypothesis is false.
- hnaccount_rng 4y ago
  I was on a workshop once where the topic was entropy and somehow we got into a discussion regarding Maxwell's Damon... This strongly reminds me of that discussion. The problem for the Damon is, that it needs to change the state of the trap according to the state of the incoming particle. And if you just hand wave "such a decision making thing exists", then you have your contradiction. But we tried, for several days, to come up with _any_ implementation (including fantasy materials) that could conceivably exist _and_ produce that effect. And for each and every attempt to build one, we came up _immediately_ with diffusive parts, where energy _must_ be lost. We concluded, that while non of us would feel confident to _rule out_ a possible existence of Maxwell's Damon, we wouldn't _at all_ be surprised if it could be ruled out. So while you are entirely correct, with enough hand-waviness, you can build reversible computations. But I have yet to see an argument, where a _potential_ implementation of one is argued to the end.
  - mjburgess 4y ago
    It's sufficient for my purposes just to show that "bit" in a logical model and "bit" under some idealised thermodynamic thought experiment are radically different notions. Reality, i am sure, has many systems which are settable and measurable and changeable at some minimum energy... and which can interface with devices of interest. For any given problem, the limit case energy requirement is defined by the needs of the algorithm. If we require setting a highly complex input state, and if we require interactions with certain devices, then we've immediately ruled out a great deal. These systems would provide you with a certain kind of "limit-case correspondence" between "logical bits" and "ideal physical bits" --- but we dont know what this system is. You dont get it from just playing around with units, nor these kinds of thought experiments. You need to know what algorithm you're talking about, and what it's requirements are. If the algorithm is understood just to be "the whole of reality" and if we suppose that it is fundamentally just aggregates of discrete states being flipped (to me, highly unlikely).... then the energy requirements are Everything... which sum, i imagine (via energy conservation), to zero.
- User23 4y ago
  An enjoyable and approachable text with more detail on reversible computing and energy expenditure from the perspective of physics is the Feynman Lectures on Computation[1]. [1] https://www.goodreads.com/book/show/17274.Feynman_Lectures_On_Computation https://www.goodreads.com/book/show/17274.Feynman_Lectures_O...
- svnt 4y ago
  Can you provide a non-theoretical example where an extant inertial body actually does no work? I believe this is impossible. You’ve just moved the assumptions to where they frame your perspective better than that other thing which competes with your perspective.
  - mjburgess 4y ago
    Energy is always conserved. Just define the computer to be the system in which energy is conserved, and there you go. A "computer" is a formal pure-mathematics notion, it is just a certain sort of "discrete mathematical model". One can define a computational model of any physical system, and hence, find computers in which energy is conserved.
    - rad88 4y ago
      If we could formalize "observe the result" we would, and it would require exchanging energy with the computer, breaking its conservation. The only way to avoid it is to say that we were always a part of the computation, but things seem to get very odd from there. You mention elsewhere that the whole universe might be construed as a computation in which energy is conserved. Why not take the absurd reduction for what it is though, and conclude that it means there's something wrong with calling anything-at-all a computer?
      - mjburgess 4y ago
        It's not an absurd reduction, it follows from the definition of a universal turing machine. This is how completely non-empirical theoretical models of computation are: they are devices of pure mathematics. This is exactly my point. If you want to use the formal machinery of computer science to say something empirical, you cant just hijack terminology and speak in this pseudoscientific way, ie., "the brain as a computational process" (etc.). What is the empirical content of such a claim? There might be some if you defined what algorithm the brain was computing, and what the empirical correspondance between the algorithm and the brain way (etc. etc.) -- but no one is doing this. We are speaking as-if somehow "universal turing machines" had some empirical content, that there's something insightful about labelling the brain this way (vs. anything at all). There isnt.
- Schroedingersat 4y ago
  Are you trying to argue that reversible computing is classical computing, that the second law of thermodynamics doesn't exist, that modelling the brain as a classical computer/thermal process (ie. something that creates information) is presumptive, or something else? All of these concepts have been explored in depth for decades, and you don't appear to be acknowledging the existing body of work.
  - mjburgess 4y ago
    None of those things. My point is that logical models of computation dont, in themselves, have empirical content. That the language and ideas of theoretical computer science are, as with any area of pure mathematics, only empirically useful insofar as we establish how a system corresponds to a formal model.
    - Schroedingersat 4y ago
      This is patently untrue though. Information theory exists. Entropy exists. Irreversible computation is fundamentally tied to entropy increase. It doesn't matter what system you are using, if you create/delete a bit, you create heat. No known systems are limited by this, but is looming.
      - mjburgess 4y ago
        All of those words have different meanings in csci and in thermo, and in qm, and in many areas. They arent the same word. They are only connected when empirical-logical models are provided. p

mjburgess 4y ago

Sure, this is the trap of thinking of computer science as either being about computers (machines) or about science. As mostly a kind of pure discrete mathematics, we need to be careful. Consider an algorithm which says: while(true) state *= +1, state *= -1, state *= +1, ... Now, identify the +1 state as the earth when in one-half of an orbit, and the -1 as the earth in the other half. And therefore the position of the earth as the logical bit ("the state") and its movement as the change to the logical bit. This is "perpetual motion", but the technical name in physics for this is inertial motion, and its common. Motion itself doesn't require work, using that motion for work, requires work. See also https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing

sudosysgen 4y ago
If you really want to be pedantic, even infinite inertial motion isn't possible, because a true vacuum is impossible, and there is thus necessarily drag somewhere. Also, I've said that before, but we already know that brains operate under an irreversible computation model.
- User23 4y ago
  > Also, I've said that before, but we already know that brains operate under an irreversible computation model. We don't know that brains operate under any kind of computational model at all. It's often postulated, but it's not proved. Every attempt I've seen at a proof reduces to begging the question. Edit: To be clear I’m not saying a computational model of the brain can’t be a useful tool. Newtonian physics works quite well quite often even though reality isn’t Newtonian.
  - sudosysgen 4y ago
    To be clear, I'm not saying that everything the brain does can be modelled by a known computation model. All I'm saying is that the interesting part of what the brain does is computation, in that it takes in data, operates on it, and returns data. It does this in an irreversible manner because you cannot determine the input from the output (nor a significant part of it). If there is any model of how the brain works it will be a computational model. Perhaps a new one, and perhaps a radically different one, but it's still going to find the definition of a computational model.
    - User23 4y ago
      Ultimately, the open question here is this: are uncomputable functions just a mathematical fancy, or do there really exist processes that can only be fully correctly described by uncomputable functions? Personally I lean towards latter view. I’m the first to admit that I have no proof. It’s just my belief, because I find the metaphysical evidence compelling. I don’t object to investigating the former possibility, but I also don’t care for it just being baldly asserted. If the answer is affirmative, that means that science will probably never be solved and we’ll just have to content ourselves with incremental improvements in our understanding. That’s observably been the case up until now. Granted even if all processes are in fact described entirely by computable functions we might still never discover what they are. I hope it’s clear how all that relates to the concrete problem of understanding human cognition and the brain. I'm nowhere near smart enough to even begin to conceive of a mathematical framework for taming noncomputable functions in a pragmatic way, but I earnestly hope some genius comes along who is, supposing that noncomputable functions are needed to completely describe our reality.
      - sudosysgen 4y ago
        Well, those functions are called uncomputable because, as far as we know, there is no repeatable way of computing them, right? So if the human brain was able to compute functions that Turing machines can't, it doesn't mean those functions are uncomputable, it just means the Church-Turing hypothesis is false.
hnaccount_rng 4y ago
I was on a workshop once where the topic was entropy and somehow we got into a discussion regarding Maxwell's Damon... This strongly reminds me of that discussion. The problem for the Damon is, that it needs to change the state of the trap according to the state of the incoming particle. And if you just hand wave "such a decision making thing exists", then you have your contradiction. But we tried, for several days, to come up with _any_ implementation (including fantasy materials) that could conceivably exist _and_ produce that effect. And for each and every attempt to build one, we came up _immediately_ with diffusive parts, where energy _must_ be lost. We concluded, that while non of us would feel confident to _rule out_ a possible existence of Maxwell's Damon, we wouldn't _at all_ be surprised if it could be ruled out. So while you are entirely correct, with enough hand-waviness, you can build reversible computations. But I have yet to see an argument, where a _potential_ implementation of one is argued to the end.
- mjburgess 4y ago
  It's sufficient for my purposes just to show that "bit" in a logical model and "bit" under some idealised thermodynamic thought experiment are radically different notions. Reality, i am sure, has many systems which are settable and measurable and changeable at some minimum energy... and which can interface with devices of interest. For any given problem, the limit case energy requirement is defined by the needs of the algorithm. If we require setting a highly complex input state, and if we require interactions with certain devices, then we've immediately ruled out a great deal. These systems would provide you with a certain kind of "limit-case correspondence" between "logical bits" and "ideal physical bits" --- but we dont know what this system is. You dont get it from just playing around with units, nor these kinds of thought experiments. You need to know what algorithm you're talking about, and what it's requirements are. If the algorithm is understood just to be "the whole of reality" and if we suppose that it is fundamentally just aggregates of discrete states being flipped (to me, highly unlikely).... then the energy requirements are Everything... which sum, i imagine (via energy conservation), to zero.
User23 4y ago
An enjoyable and approachable text with more detail on reversible computing and energy expenditure from the perspective of physics is the Feynman Lectures on Computation[1]. [1] https://www.goodreads.com/book/show/17274.Feynman_Lectures_On_Computation https://www.goodreads.com/book/show/17274.Feynman_Lectures_O...
svnt 4y ago
Can you provide a non-theoretical example where an extant inertial body actually does no work? I believe this is impossible. You’ve just moved the assumptions to where they frame your perspective better than that other thing which competes with your perspective.
- mjburgess 4y ago
  Energy is always conserved. Just define the computer to be the system in which energy is conserved, and there you go. A "computer" is a formal pure-mathematics notion, it is just a certain sort of "discrete mathematical model". One can define a computational model of any physical system, and hence, find computers in which energy is conserved.
  - rad88 4y ago
    If we could formalize "observe the result" we would, and it would require exchanging energy with the computer, breaking its conservation. The only way to avoid it is to say that we were always a part of the computation, but things seem to get very odd from there. You mention elsewhere that the whole universe might be construed as a computation in which energy is conserved. Why not take the absurd reduction for what it is though, and conclude that it means there's something wrong with calling anything-at-all a computer?
    - mjburgess 4y ago
      It's not an absurd reduction, it follows from the definition of a universal turing machine. This is how completely non-empirical theoretical models of computation are: they are devices of pure mathematics. This is exactly my point. If you want to use the formal machinery of computer science to say something empirical, you cant just hijack terminology and speak in this pseudoscientific way, ie., "the brain as a computational process" (etc.). What is the empirical content of such a claim? There might be some if you defined what algorithm the brain was computing, and what the empirical correspondance between the algorithm and the brain way (etc. etc.) -- but no one is doing this. We are speaking as-if somehow "universal turing machines" had some empirical content, that there's something insightful about labelling the brain this way (vs. anything at all). There isnt.
Schroedingersat 4y ago
Are you trying to argue that reversible computing is classical computing, that the second law of thermodynamics doesn't exist, that modelling the brain as a classical computer/thermal process (ie. something that creates information) is presumptive, or something else? All of these concepts have been explored in depth for decades, and you don't appear to be acknowledging the existing body of work.
- mjburgess 4y ago
  None of those things. My point is that logical models of computation dont, in themselves, have empirical content. That the language and ideas of theoretical computer science are, as with any area of pure mathematics, only empirically useful insofar as we establish how a system corresponds to a formal model.
  - Schroedingersat 4y ago
    This is patently untrue though. Information theory exists. Entropy exists. Irreversible computation is fundamentally tied to entropy increase. It doesn't matter what system you are using, if you create/delete a bit, you create heat. No known systems are limited by this, but is looming.
    - mjburgess 4y ago
      All of those words have different meanings in csci and in thermo, and in qm, and in many areas. They arent the same word. They are only connected when empirical-logical models are provided. p