Editing Linear speedup theorem (section)

== Dependence on the shape of storage ==
[[Kenneth W. Regan|Regan]]<ref>{{cite journal |last1=Regan |first1=Kenneth W. |title=Linear time and memory-efficient computation |journal=SIAM Journal on Computing |date=1996 |volume=25 |issue=1 |pages=133–168}}</ref> considered a property of a computational model called information vicinity. This property is related to the memory structure: a Turing machine has linear vicinity, while a [[Pointer machine#KUM|Kolmogorov-Uspenskii machine]] and other [[pointer machine]]s have an exponential one. Regan’s thesis is that the existence of linear speedup has to do with having a polynomial information vicinity. The salient point in this claim is that a model with exponential vicinity will not have speedup even if changing the alphabet is allowed (for models with a discrete memory that stores symbols). Regan did not, however, prove any general theorem of this kind. Hühne <ref>{{cite journal |last1=Hühne |first1=Martin |title=Linear Speed-Up Does not Hold on Turing Machines with Tree Storages |journal=Information Processing Letters |date=1993 |volume=47 |issue=6 |pages=313–318 |doi=10.1016/0020-0190(93)90078-N}}</ref> proved that if we require the speedup to be obtained by an on-line simulation (which is the case for the speedup on ordinary Turing machines), then linear speedup does not exist on machines with '''tree storage'''.