proj-plbook-plChPhysics

Reversible computing

• http://my.safaribooksonline.com/book/electrical-engineering/computer-engineering/9781439873410/chapter-18-reversible-instruction-set-architectures/chapter_18_reversible_instruct#X2ludGVybmFsX0J2ZGVwRmxhc2hSZWFkZXI/eG1saWQ9OTc4MTQzOTg3MzQxMC8yNjI=
• Introduction to Reversible Computing By Kalyan S. Perumalla) (in addition to the below, has chapter on reversible programming languages (Chapter 8), alternative integer framework for reversibility (section 14.6), reversible instruction set architecture (chapter 18, see below))
• Toffoli gate (CCNOT) (first reversible gate mentioned in Introduction to Reversible Computing By Kalyan S. Perumalla) "It has 3-bit inputs and outputs; if the first two bits are set, it inverts the third bit, otherwise all bits stay the same." -- http://en.wikipedia.org/wiki/Toffoli_gate . CCNOT is universal for classical computation [1]
• "Any reversible gate must have the same number of input and output bits, by the pigeonhole principle. For one input bit, there are two possible reversible gates. One of them is NOT. The other is the identity gate which maps its input to the output unchanged. For two input bits, the only non-trivial gate is the controlled NOT gate which XORs the first bit to the second bit and leaves the first bit unchanged. Unfortunately, there are reversible functions that cannot be computed using just those gates. In other words, the set consisting of NOT and XOR gates is not universal. If we want to compute an arbitrary function using reversible gates, we need another gate. One possibility is the Toffoli gate, proposed in 1980 by Toffoli...The Toffoli gate is universal" -- http://en.wikipedia.org/wiki/Toffoli_gate
• the CNOT gate is probably the "the controlled NOT gate which XORs the first bit to the second bit and leaves the first bit unchanged"
• Fredkin gate (CSWAP) universal "The Fredkin gate is the three-bit gate that swaps the last two bits if the first bit is 1." http://en.wikipedia.org/wiki/Fredkin_gate . CSWAP is universal for classical computation [2]
• Pendulum (first mentioned in Introduction to Reversible Computing By Kalyan S. Perumalla)
• Janus programming language ('the best example of a reversible compiler' according to Introduction to Reversible Computing By Kalyan S. Perumalla)
• book notes that if a default value of 'zero' is assumed for memory locations, then you can copy into a location containing only zeros as long as you just rememeber that it was empty before
• i managed to read much of section 18.1, Instruction Set Issues, and 18.2, PDP-10-Like Instruction Set Architecture, in Safari preview:
• "addition, for exam- ple, is deﬁned as an accumulation operation with two operands (A ← A+B) or overwriting operation with three operands (C ← A+B). The accumulation instruction is undone by the inverse instruction (A ← A−B?), while the over- writing operation is undone by lossless erasure (C ← C XOR (A + B), where XOR is an exclusive-OR bit operation). Analogous reversible set of instructions are provided for bit-level operations of AND, OR, NOT, and EXCLUSIVE OR, such that irreversible binary operations require three operands while reversible unary or binary operations are deﬁned with two operands. Some instruction sets make a distinction between arithmetic and logic operations; however, for simplicity, we view them as belonging to the same class "
• "These up- dates to the program counter are themselves made reversible using reversible arithmetic instructions. In the case of multiple jumps to the same destina- tion label, disambiguation can be made by making use of a new variable with ⌈logJL⌉ bits, where JL is the number of diﬀerent jumpto instructions with the same destination label L"
• "Noting the symmetry of the jumpto and jumpfrom instructions, an implementation may merge both..into one.. called branch..provided there is a way to consult the current direction of control flow separately, say, via a special register bit that holds 0 for forward direction and 1 for reverse direction. Thus, a single branch instruction is sufficient... if (1) the current direction of flow is available separately, and (2) the destination of every branch instruction is guaranteed to be another branch instruction." (preview ends here, skip to page 265) -- 18.1.4
• table 18.1 "Memory Operations in PDP-10-Like Reversible Instruction Set Architecture: Instruction Description EXCH A, B Exchanges the values in A and B. COPY A, B Copies the value of B into A. The destination is re- quired to be zero before the operation. MOVE A, B Moves the value of B into A. The destination is re- quired to be zero before the operation, and the source is zeroed after the operation. ERASE A This is an irreversible operation that zeros the contents of the given location"
• 18.2.3 Branches: jumpto and comefrom instructions conditional on the usual (gt, ge eq, le, lt, ne). note that for reversibility the variable that was conditioned upon may not be modified during any conditionally executed code
• alternative integer framework for reversibility: page 227: http://my.safaribooksonline.com/book/electrical-engineering/computer-engineering/9781439873410/chapter-18-reversible-instruction-set-architectures/227 the internal representation of integers is two bit fields, A and L. A is a bit field of bit width w, split into two parts, R and Qhat, and L is another bit field also called q. L (q), of bit width l, tells how many bits are in R and how many are in Qhat, e.g. defines the boundary between R and Qhat within A. section 14.6.3, two pages later, says that the value stored is Q*v+R, where Q is the base. Section 14.6.6, two pages later, say that Q = 2^q - 1 + Qhat for the largest possible q, 0 <= q <= w. Example: say that R is 01011 and Qhat is 010 and L is 0011. So w = 8, 2^w = 256, l = 4, q = 3, Qhat = 2, Q = 9, R = 11. So, if the base is e.g. 15, we have 9*15 + 11 = 146.
• table 14.5, page 232: A New Set of Alternative Arithmetic Operations Reversible without Generating History. "Typical forward" operations are A' <- A + B; A' <- A - B; A' <- A * B; A' <- A / B; A' <- A mod B; for each of these it shows how to compute them, although i can't read the notation.
• 6.4 Definition of a revirsible model "The two sources of irreversibilitywere overcomeby Bennett using the following steps:  A new spontaneous transition possibility is introduced by adding a spe- cial solidus symbol (/), which acts as a wild card, matching any symbol at the current tape head; alternatively, the action of solidus can be viewed as not reading the tape or ignoring the current symbol.  The form of transition rules is redeﬁned to split the combined write and move operations into two separate rules, one for writing and the other for moving the head.  The machine formalism is generalized to accommodate multiple tapes instead of the single tape of the conventional model.
• The transition rules are relaxed to accommodate multi-head opera- tion, by changing the symbols and tape movement speciﬁcations into k-element vectors (for k tapes) instead of scalars for 1-tape operation.  The machine is augmented with two additional tapes: the original work- ing tape, a new tape called the history tape, and another called the output tape. "
• TOC of chapter 8, Reversible programming languages, mentions SRL and ESRL, EPA, Janus, R within section 8.3, Procedural languages. Section 8.4, Page 125 convers functional and logic languages, but i can only read the first half of that page. Page 126, a continuation of that section, cites Baker and mentions Zuliani's pGCL (probabalistic guarded-command language) and Fun, Inv, LRInv by Mu et al, Gluck and Kawabe. Section 8.5, further reading, doesn't mention any others. A list on page 105 (section 8.2) has Janus, R, EPA, SRL, ESRL, PSILISP, INTERLISP, INV, pGCL, in that order.
• section 8.2.2 Destructive updates. Defines destructive updates and gives an example, then gives an example of a non-destructive ('constructive') update, swap. "Reversible languages must prohibit any expression e that is not possible to symbolically invert, and restrict updates to invertible operators. For example, only invertible operations such as swap, increment, and decrement may be deﬁned by the language, and the language syntax may be deﬁned to make it impossible to express any destructive update."
• "8.2.3 Arithmetic In conventional computers, arithmetic is in general irreversible. To ensure re- versibility, arithmetic-based modiﬁcations must be restricted to be construc- tive in nature, such as simple accumulations or decrements (+= and -=). More general solutions include relaxations and redeﬁnitions of multiplication and di- vision operations to eliminate all possibilities of overﬂow and underﬂow that lose information. For example, the semantics of multiplication may be rede- ﬁned to employ three operands instead of two operands, to address all sources of irreversibility. Modulo arithmetic is another important component of re- versible arithmetic."
• "8.2.4 Conditionals Branches of control ﬂow due to conditionals have the potential to introduce irreversibility because they can create ambiguity on the backward path at the point at which forward branches converge. Conditional statements introduce a split of control ﬂow into two or more branches, which are then merged into a single ﬂow later in the execution. When executing in reverse, information is needed at the merge point as to which of the branches must be traversed in reverse. "
• how to deal with it; make the programmer give a pragma at each branch that chooses: " (1) there is no reversibility hazard, that is, C1 and C2 are both assured to be null sets; or (2) a post-branch expression is speciﬁed that can recover the pre-branch expression’s truth value; or (3) the compiler must generate a temporary bit variable that records the forward pre-branch truth value, which should be used in the reverse execution. The default could be the last option, so if the programmer does not specify the ﬁrst or second, the compiler automatically inserts the bit needed to remember the branching decision. The language can permit the speciﬁcation of the programmer’s option via a pragma interface."
• 8.2.5 Loops (can't read the first part of this); solutions (one that i can't read, and then: " terminated in reverse. Forward assert epre while not epost do S assert not epre Reverse assert epost while not epre do S−1 assert not epost 2. Counter-Based Reversal In this approach, a new temporary variable is introduced by the compiler to remember the number of times the loop body was executed in the forward mode. Forward c ← 0 while e do S c ← c + 1 Reverse while c > 0 do S−1 c ← c−1 3. Pragma Speciﬁcations A language interface can be used by the pro- grammer to specify a symbolic stopping condition expression that the reverse mode execution can use to terminate the loop during execution. The compiler inserts this expression into the reverse loop. Alternatively, the name of a variable that maintains the loop count in the program can be speciﬁed, so that no new variable needs to be introduced by the compiler. If the programmer does not specify either option, the compiler automatically inserts the counter variable needed to remember the loop count. The language can enable the speciﬁcation of the programmer’s options via a pragma interface. For example, #pragma LOOP CONDITION expression just before the while statement applies the ﬁrst option to that statement, while #pragma LOOP COUNTER variable speciﬁes the second option, and #pragma LOOP COUNTER "AUTOMATIC" speciﬁes the third option. 4. Restriction of Semantics In this approach (which may be considered draconian), no support for variable iteration is provided. Loops with a ﬁxed number of iterations are allowed. Although highly restrictive in nature, this approach does still allow many algorithms to be eﬀectively expressed in terms of loops with ﬁxed iteration counts. Algorithms such as sorting and Fourier transforms can indeed be expressed under such restriction of semantics, with the added assurance of reversibility. Some reversible languages have been deﬁned in the literature with such a con- straint and used for the purposes of theoretical analyses. "
• 8.2.6 Other control flow issues

"

• Jump instructions such as goto statements can be made reversible by diﬀerent solutions. One way is the introduction of a reverse-peer instruc- tion such as comefrom. Another method is to prevent statements from being targets of more than one jump instruction. Yet another method is to have the compiler generate certain disambiguating variables that keep track of the origin of the jump when the jump is potentially made from multiple origin points.  Reversal of procedure calls is achieved by one of two ways, depending on the speciﬁc language support used. In languages in which every state- ment is reversible, there is only one instance of the procedure that can be executed in forward or reverse mode. Moreover, in some languages, a procedure can in fact be called or “uncalled” in forward mode itself. The corresponding calls become reversed so that the procedure becomes uncalled or called, respectively, in reverse mode. In languages that gen- erate two separate instances of the procedure, one for forward execution and the other for reverse execution, the invocation of a (forward in- stance) procedure call in forward mode gets reversed by invocation to the reverse instance of the procedure.
• Recursion is naturally handled by the same techniques as for a subroutine call " (there are more bullet points but i can't read them)
• Toffoli on Reversible Computing: http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-151.pdf
• Pendulum: http://dspace.mit.edu/bitstream/handle/1721.1/36039/33342527.pdf
• (add register register) (addu register register) (sub register register) (subu register register) (and_op register register) (or_op register register) (xor_op register register) (nor_op register register) (slt register register) (sltu register register) (sll register int) (srl register int) (sra register int) (sllv register register) (srlv register register) (srav register register) (rl register int) (rr register int) (rlv register register) (rrv register register) (j absolute-target) (jr register) (jal register relative-target) (jalr register relative-target) (bltz register relative-target) (bgez register relative-target) (bltzal register register relative-target) (bgezal register register relative-target) (beq register register relative-target) (bne register register relative-target) (blez register relative-target) (bgtz register relative-target) (cf) (addi register int) (addiu register int) (slti register int) (sltiu register int) (andi register int) (ori register int) (xori register int) (exchange register register) -- http://web.mit.edu/~deberg/emacs/elisp/pendasm.el
• "The instruction set is nearly identical to that of a conventional processor with the notable exceptions of "come-from" and "exchange." Pendulum memory accesses are handled with the single exchange instruction. Pendulum supports a full set of arithmetic and logical operations, shifts and rotates, both on reg- ister values and instruction immediates. Control flow is achieved through a number of unconditional and conditional jumps and branches, including linking jumps and jump-to- register-value. Unlike many conventional processors, Pendulum supports rotate instructions as well as standard shift instructions. Shift is a garbage creating instruction because information is lost when bits are shifted off the end of a word. A rotate instruction transfers the bits to the other end of the word, retaining the information. If a small number is shifted left a small amount, the right (least significant) bits are filled with zeros. This is identical to a rotate operation. Likewise, a number may be shifted to the right if the low order bits are zero and the number being shifted is either non-negative or logically shifted (zero filled in the high order bits), by performing a rotate. Knowing the range of values of a number is required to replace shift with rotate, of course, but in the common case of left-shifting a small number, rotate may be used to reduce garbage.

Whenever possible, programs should be structured to make use of the non-garbage creating instructions and avoid the few irreversible operations: shifts, set-on-less-than, AND, OR, and NOR. " note that for reversibility in Pendulum, jumps may only target addresses directly following a comefrom.

Quantum computing

http://en.wikipedia.org/wiki/Quantum_computer

http://en.wikipedia.org/wiki/Quantum_Turing_machine

http://en.wikipedia.org/wiki/Quantum_programming