Linear Speed-Up, Information Vicinity, and Finite-State Machines
Kenneth W. Regan · 1994
Connections are shown between two properties of a machine model: linear speed-up and polynomial vicinity . In the context of the author's Block Move (BM) model, these relate to: "How long does it take to simulate a finite transducer S on a given input z?" This question is related to the century-old problem of finding economical representations for finite groups. Under some cost measures for computing S(z), the BM enjoys the linear speed-up property, but under more-realistic measures, and subject to a reasonable but unproved hypothesis, it has the antithetical property of a constant-factor time hierarchy . 1 Speed-Up and Vicinity Hartmanis and Stearns [HS65] proved that the standard multitape Turing machine (TM) model enjoys the following property, for which we give a general statement: Definition 1.1. A machine model M has the linear speed-up property if there exists k 0 ? 0 such that for every ffl ? 0 and t(n) time-bounded M-machine M , there exists a M-machine M 0 that computes...