Одно свойство емкостной сложности вычислений при унарной записи натуральных чисел

Abstract

Memory computational complexity of every recursive function ƒ(x1,…,xn) is bounded by a linear polynomial P(x1,x2,…,xn, ƒ(x1,…,xn-1,mi), ƒ(x1,…,xn),mi,mj), (mi<xn,mi≤ ƒ(x1,…,xn)) when natural numbers are represented by words 1(n)(n≥1).