Arbitrary sequence RAMs

DOI10.1016/J.IPL.2014.09.010zbMATH Open1302.68115arXiv1310.4588OpenAlexW2092899023MaRDI QIDQ477622FDOQ477622

Authors: Michael Brand 

Publication date: 9 December 2014

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

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.

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

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

zbMATH Keywords

computational complexitytheory of computationarbitrary numberarithmetic complexityrandom access machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Fast exponentiation using the truncation operation
• Lower Bounds for Computations with the Floor Operation
• Title not available (Why is that?)
• Factoring numbers in O(log n) arithmetic steps
• On Faster Integer Calculations Using Non-arithmetic Primitives
• Title not available (Why is that?)
• Title not available (Why is that?)
• Division in idealized unit cost RAMs
• On the power of the shift instruction
• Title not available (Why is that?)
• A lower bound for integer greatest common divisor computations
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Title not available (Why is that?)
• Computing with and without Arbitrary Large Numbers
• On undecidable statements in enlarged systems of logic and the concept of truth

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)