Division Is Good

We study the power of RAM acceptors with several instruction sets. We exhibit several instances where the availability of the division operator increases the power of the acceptors. We also show that in certain situations parallelism and stochastic features ('distributed random choices') are provably more powerful than either parallelism or randomness alone. We relate the class of probabilistic Turing machine computations to random access machines with multiplication (but without boolean vector operations). Again, the availability of integer division seems to play a crucial role in these results.

Authors

• Janos Simon

Keywords

• Turing machines
• Concurrent computing
• Read-write memory
• Parallel processing
• Distributed computing
• Instruction sets
• Stochastic processes
• Computational modeling
• Polynomials
• Magnetic heads
• Educational Settings
• Boolean Operators
• Stochastic Character
• Turing Machine
• Results Section
• Computational Model
• Random Number
• Time Constant
• Probabilistic Model
• Proof Of Theorem
• Random Generation
• Stochastic Model
• Language Teaching
• Machine Model
• Arithmetic Operations
• Power-of-two
• String Length
• Extra Power
• Random String
• Acceptable Definition
• Universal Quantifier