Space measures for storage modification machines (Q1119021)

Storage modification machines (SMM) and Kolmogorov-Uspenskii machines (KUM) do belong to the first machine class (mutual simulations with polynomial time overhead and constant factor space overhead are possible) only if they are equipped with an artificial space measure, i.e. space n log n is charged for n nodes. This follows from the result proved in this paper, that Turing machine space s(n) log s(n) is equivalent to both SMM space 0(s(n)) and to KUM space 0(s(n)) under the uniform space measure for the latter machines (i.e. space n is charged for n nodes).