Efficient on-Line Simulations of Tree Machines and Multidimensional Turing Machines by Random Access Machines
Abstract
The random access machine (RAM) and the Turing machine (TM) are the standard models for sequential computation. Research into the use to time and space by these and other models gives us insight into their computational power. This research includes analyzing how two different models use time and space, and comparing time and space utilization within a single model. Another avenue of investigation is determining how altering the definitions of time and space (for example, log-cost versus unit-cost) for a model affects its computational power. Slot and van Emde Boas (1988), for example , showed how space equivalence of RAMs and Turing machines is affected by varying the definition of space complexity for RAMs. We present an on-line simulation of a tree machine of time complexity t by a log-cost RAM of time complexity O((T log T)/log log t). Using the notion of incompressibility from Kolmogorov complexity (Li and Vitanyi, 1988), we show that this simulation is optimal. This appears to be the first application of Kolmogorov complexity to sequential RAMs. It is significant because few algorithms have been shown to be optimal. This work is a complement to Loui's (1983) simulation of tree machines by multidimensional Turing machines and Reischuk's (1982) simulation of multidimensional Turing machines by tree machines.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 24, 1989
- Accession Number
- ADA213152
Entities
People
- David R. Luginbuhl
- Michael C. Loui
Organizations
- University of Illinois Urbana–Champaign