Arbitrary sequence RAMs

DOI10.1016/J.IPL.2014.09.010MaRDI QIDQ477622zbMATH OpenOpenAlexFDO

Authors Michael Brand

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.4588

zbMATH Keywords

computational complexitytheory of computationarbitrary numberarithmetic complexityrandom access machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: It is known that in some cases a Random Access Machine (RAM) benefits from having an additional input that is an arbitrary number, satisfying only the criterion of being sufficiently large. This is known as the ARAM model. We introduce a new type of RAM, which we refer to as the Arbitrary Sequence RAM (ASRAM), that generalises the ARAM by allowing the generation of additional arbitrary large numbers at will during execution time. We characterise the power contribution of this ability under several RAM variants. In particular, we demonstrate that an arithmetic ASRAM is more powerful than an arithmetic ARAM, that a sufficiently equipped ASRAM can recognise any language in the arithmetic hierarchy in constant time (and more, if it is given more time), and that, on the other hand, in some cases the ASRAM is no more powerful than its underlying RAM.

Recommendations

• Computing with and without arbitrary large numbers
• P-RAM vs. RP-RAM
• Parallelism in random access machines
• scientific article; zbMATH DE number 3954278
• Lower bounds on algebraic random access machines

Cites work

• scientific article; zbMATH DE number 3757704 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• scientific article; zbMATH DE number 3592964 (Why is no real title available?)
• scientific article; zbMATH DE number 3637287 (Why is no real title available?)
• scientific article; zbMATH DE number 4117838 (Why is no real title available?)
• A lower bound for integer greatest common divisor computations
• Computing with and without arbitrary large numbers
• Division in idealized unit cost RAMs
• Factoring numbers in O(log n) arithmetic steps
• Fast exponentiation using the truncation operation
• Lower Bounds for Computations with the Floor Operation
• On Faster Integer Calculations Using Non-arithmetic Primitives
• On the power of the shift instruction
• On undecidable statements in enlarged systems of logic and the concept of truth
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

Cited in

(1)

• Computing with and without arbitrary large numbers

This page was built for publication: Arbitrary sequence RAMs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477622)