Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The original Rojas paper can be found <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.665&amp;rep=rep1&amp;type=pdf" rel="noreferrer">here</a>. The basic idea is that the Z3 only supports a unconditional single loop (by gluing the ends of the instruction tape together). You build conditional execution of it by putting all code sections one after another in the loop, and having a variable z that determines which section to execute. At the beginning of section j, you set</p> <pre><code> if (z==j) then t=0 else t=1 </code></pre> <p>and then make each assignment <code>a = b op c</code> in this section read</p> <pre><code> a = a*t + (b op c)*(1-t) </code></pre> <p>(i.e. each assignment is a no-op, except in the active section). Now, this still includes a conditional assignment: how to compare z==j? He proposes to use the binary representation of z (z1..zm) along with the negated binary representation of j (c1..cm), and then compute</p> <pre><code>t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm)) </code></pre> <p>This product will be 1 only if c and z differ in all bits, which will happen only if z==j. An assignment to z (which essentially is an indirect jump) must also assign to z1..zm.</p> <p>Rojas has also written <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.757&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Conditional Branching is not Necessary for Universal Computation in von Neumann Computers</a>. There he proposes a machine with self-modifying code and relative addressing, so that you can read the Turing instructions from memory, and modify the program to jump accordingly. As an alternative, he proposes the above approach (for Z3), in a version that only uses LOAD(A), STORE(A), INC and DEC.</p>
    singulars
    1. This table or related slice is empty.
    1. POIs conditional branching a requirement of Turing-completeness?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USMartin v. Löwis
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POIs conditional branching a requirement of Turing-completeness?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COI like your answer, but what happens when the machine can't do arithmetic? Or if the machine is somewhat reminiscent of a ZISC? Thank you!
      singulars
      1. PO
      1. USDavid Titarenco
    2. CODefine "arithmetic". The usual definition would, at a minimum, include addition. The (second) Rojas machine doesn't have addition, only INC (he also discusses that DEC isn't needed). In any case, I can't provide a proof that a ZISC without a conditional instruction would or would not be Turing-complete; I personally believe it would not.
      singulars
      1. PO
      1. USMartin v. Löwis
    3. COThank you for your insight!
      singulars
      1. PO
      1. USDavid Titarenco
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload