Linear speed-up does not hold on Turing machines with tree storages

DOI10.1016/0020-0190(93)90078-NzbMATH Open0788.68060MaRDI QIDQ688445FDOQ688445

Authors: Martin Hühne 

Publication date: 20 December 1993

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

Recommendations

• scientific article; zbMATH DE number 6292628
• A speed-up theorem without tape compression
• Fast Simulation of Turing Machines by Random Access Machines
• scientific article
• The hedge: an efficient storage device for Turing machines with one head

zbMATH Keywords

computational complexitylower boundsKolmogorov complexityTuring machinesspeed-uponline simulationtree storage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• On the Computational Complexity of Algorithms
• Relations Among Complexity Measures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Boolean Memories
• On time versus space. II
• A fast implementation of a multidimensional storage into a tree storage
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• Optimal Dynamic Embedding of Trees into Arrays
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal On-Line Simulations of Tree Machines by Random Access Machines
• On the Minimum Computation Time of Functions
• Minimizing access pointers into trees and arrays

Cited In (1)

• Space measures for storage modification machines

This page was built for publication: Linear speed-up does not hold on Turing machines with tree storages

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