5 ms·

Embracing the Laws of Physics: Three Reversible Models of Computation

70 points by adamnemecek 8y ago

scentoni 8y ago
for background: https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Fredkin_gate https://en.wikipedia.org/wiki/Fredkin_gate https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate
- Cobord 8y ago
  Shameless Plug: https://arxiv.org/abs/1810.08865 https://arxiv.org/abs/1810.08865
User23 8y ago
The Feynman lectures on Computation provide good background on reversible computation from the perspective of a brilliant physicist. https://www.scribd.com/doc/52657907/Feynman-Lectures-on-Computation https://www.scribd.com/doc/52657907/Feynman-Lectures-on-Comp...
whatshisface 8y ago
>>Proposition IV. That axiom of metaphysicians which is termed the principle of contradiction, and which affirms that it is impossible for any being to possess a quality, and at the same time not to possess it, is a consequence of the fundamental law of thought, whose expression is x^2=x >This “law” is reasonable in a classical world but is violated by the postulates of quantum mechanics I think this might be a little bit of a stretch, if a particle is in a superposition of states it's not contradictory about which state it is in, it's just in a superposition of both. I think a good analogy for that would be your keyboard, which is located at the Q key as well as the M key.
WAthrowaway 8y ago
Hmm would software like Nix function as a practical example of 'reversible computing'?
- qubex 8y ago
  No: Reversible Computing embraces the (quantum mechanical) notion that information cannot ever be lost (cfr the “Black Hole Information Paradox”), and that therefore the output of a computation can only be a reshuffled but complete permutation of the input. Nix (for example) allows you to delete stuff and/or initialise a variable by zeroing it out and thus obliterating information. A reversible computing paradigm would not allow this. (In practical terms this information is dissipated as heat when memory deletes information.)
  - krastanov 8y ago
    I am confused by the downvotes. The above post is correct even if not using the clearest of phrasings. But I would like to nitpick: You really do not need to involve quantum mechanics. These effects are present in classical thermodynamics. They are just more explicit in quantum mechanics.
  - WAthrowaway 8y ago
    Thank you for the insight, that makes a lot of sense! I just ordered the Feynman Lectures on Computation, excited to read.
deleted 8y ago
[deleted]
evincarofautumn 8y ago
The language they introduce, Π, is essentially a simple concatenative programming language where all of the primitive combinators happen to be reversible; the graphical depiction is essentially the same as graphical linear algebra¹, which is no coincidence. Concatenative combinator calculus is related to combinatory logic—specifically, it’s a variation that replaces application of combinators with composition, leading to a bunch of nice mathematical properties. Both of these logics have the nice feature that you can syntactically restrict the substructural rules of contraction (dropping), exchange (swapping), and weakening (copying): for example, a well-formed program that doesn’t use the K combinator to drop a value is guaranteed to be linear, i.e., not destroy any information. This isn’t true in ordinary lambda calculus, where you can use a variable zero or many times, so you need additional checks on the uses of a variable to determine whether a function is linear, affine, &c. I like the theory of concatenative programming languages because they provide an elegant compositional/dataflow-oriented style of programming, have deep connections to linear logic, Hughes’ “arrows”, effects & coeffects, and quantum/reversible computation, while also admitting very efficient implementation on classical hardware. I’m (very slowly) working on a statically typed low-level concatenative language that’s meant to provide all the nice high-level typed functional language features like higher-order functions, pipeline-style programming, and effects tracked in the types, while requiring no runtime support such as a tracing garbage collector—the ultimate goal is to allow a restricted subset that doesn’t even require a heap allocator, so you could use it to implement e.g. a kernel or device firmware. I hope that concatenative languages find their way to the mainstream as the basis for programming quantum and extremely low-power computing devices (which we will need in order to reduce emissions). ¹ https://graphicallinearalgebra.net/ https://graphicallinearalgebra.net/
scottlocklin 8y ago
" both these fundamental physical theories imply that information is a conserved quantity of physical processes and hence of primitive computational operations." No, actually they do not. Jayzus. Peer review is obviously dead.
- foxes 8y ago
  Anyone can post on arxiv. Quantum computation is reversible in terms of applying unitary gates to qubits. However doing IO - breaking entangled states, or interacting with the outside world, is not reversible in a practical sense.
  - rbanffy 8y ago
    Or, as I like to joke, you can't tell a purely functional program ran because it had no side effects.
  - scottlocklin 8y ago
    Like classical reversible computing (which theoretically can mean P=NP), quantum computation fails to exist in the actual world; probably for the same reasons. I think it's not quite true anyone can post on arxiv, and I wager 10 quatloos that this goes into some non-obscure physics journal and is presented to great acclaim, despite being as dumb as a bag of hammers.

70 points by adamnemecek 8y ago

for background: https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Fredkin_gate https://en.wikipedia.org/wiki/Fredkin_gate https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate

Cobord 8y ago
Shameless Plug: https://arxiv.org/abs/1810.08865 https://arxiv.org/abs/1810.08865

User23 8y ago

The Feynman lectures on Computation provide good background on reversible computation from the perspective of a brilliant physicist. https://www.scribd.com/doc/52657907/Feynman-Lectures-on-Computation https://www.scribd.com/doc/52657907/Feynman-Lectures-on-Comp...

whatshisface 8y ago

>>Proposition IV. That axiom of metaphysicians which is termed the principle of contradiction, and which affirms that it is impossible for any being to possess a quality, and at the same time not to possess it, is a consequence of the fundamental law of thought, whose expression is x^2=x >This “law” is reasonable in a classical world but is violated by the postulates of quantum mechanics I think this might be a little bit of a stretch, if a particle is in a superposition of states it's not contradictory about which state it is in, it's just in a superposition of both. I think a good analogy for that would be your keyboard, which is located at the Q key as well as the M key.

WAthrowaway 8y ago

Hmm would software like Nix function as a practical example of 'reversible computing'?

qubex 8y ago
No: Reversible Computing embraces the (quantum mechanical) notion that information cannot ever be lost (cfr the “Black Hole Information Paradox”), and that therefore the output of a computation can only be a reshuffled but complete permutation of the input. Nix (for example) allows you to delete stuff and/or initialise a variable by zeroing it out and thus obliterating information. A reversible computing paradigm would not allow this. (In practical terms this information is dissipated as heat when memory deletes information.)
- krastanov 8y ago
  I am confused by the downvotes. The above post is correct even if not using the clearest of phrasings. But I would like to nitpick: You really do not need to involve quantum mechanics. These effects are present in classical thermodynamics. They are just more explicit in quantum mechanics.
- WAthrowaway 8y ago
  Thank you for the insight, that makes a lot of sense! I just ordered the Feynman Lectures on Computation, excited to read.

deleted 8y ago

[deleted]

evincarofautumn 8y ago

The language they introduce, Π, is essentially a simple concatenative programming language where all of the primitive combinators happen to be reversible; the graphical depiction is essentially the same as graphical linear algebra¹, which is no coincidence. Concatenative combinator calculus is related to combinatory logic—specifically, it’s a variation that replaces application of combinators with composition, leading to a bunch of nice mathematical properties. Both of these logics have the nice feature that you can syntactically restrict the substructural rules of contraction (dropping), exchange (swapping), and weakening (copying): for example, a well-formed program that doesn’t use the K combinator to drop a value is guaranteed to be linear, i.e., not destroy any information. This isn’t true in ordinary lambda calculus, where you can use a variable zero or many times, so you need additional checks on the uses of a variable to determine whether a function is linear, affine, &c. I like the theory of concatenative programming languages because they provide an elegant compositional/dataflow-oriented style of programming, have deep connections to linear logic, Hughes’ “arrows”, effects & coeffects, and quantum/reversible computation, while also admitting very efficient implementation on classical hardware. I’m (very slowly) working on a statically typed low-level concatenative language that’s meant to provide all the nice high-level typed functional language features like higher-order functions, pipeline-style programming, and effects tracked in the types, while requiring no runtime support such as a tracing garbage collector—the ultimate goal is to allow a restricted subset that doesn’t even require a heap allocator, so you could use it to implement e.g. a kernel or device firmware. I hope that concatenative languages find their way to the mainstream as the basis for programming quantum and extremely low-power computing devices (which we will need in order to reduce emissions). ¹ https://graphicallinearalgebra.net/ https://graphicallinearalgebra.net/

scottlocklin 8y ago

" both these fundamental physical theories imply that information is a conserved quantity of physical processes and hence of primitive computational operations." No, actually they do not. Jayzus. Peer review is obviously dead.

foxes 8y ago
Anyone can post on arxiv. Quantum computation is reversible in terms of applying unitary gates to qubits. However doing IO - breaking entangled states, or interacting with the outside world, is not reversible in a practical sense.
- rbanffy 8y ago
  Or, as I like to joke, you can't tell a purely functional program ran because it had no side effects.
- scottlocklin 8y ago
  Like classical reversible computing (which theoretically can mean P=NP), quantum computation fails to exist in the actual world; probably for the same reasons. I think it's not quite true anyone can post on arxiv, and I wager 10 quatloos that this goes into some non-obscure physics journal and is presented to great acclaim, despite being as dumb as a bag of hammers.