# Restrictions to counter machines capturing LBA

As you know in computation theory, there is a simple programming language equivalent in power to Turing machines. It is described as follows:

Values: natural numbers only, but of unlimited precision.

• Variables:

– Input variables X1, X2, X3, . . .

– An output variable Y

-Local variables Z1, Z2, Z3, . . .

• Instructions:

1 ) $V ← V + 1$ Increase by 1 the value of the variable V .

2 ) $V ← V − 1$ If the value of V is 0, leave it unchanged; otherwise decrease by 1 the value of V.

3 ) $IF \;V \neq 0\; GOTO \;L$ , If the value of V is nonzero, perform the instruction with label L next; otherwise proceed to the next instruction in the list.

• Labels: A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, . . .

• Exit label: E.

• All variables and labels are in the global scope .

for example the following program computes f(x) such that if x = 0 , f(x) = 1 otherwise f(x) = x \begin{align} [A] \quad &X ← X − 1 \\ &Y ← Y + 1 \\ &IF\; X \neq 0\; GOTO \;A \\ \end{align} this language can use infinite number of variables.

What restrictions should be added to this language so its power will be the same as Linear Bounded Automata? One of them is clear about the variables but I will appreciate if anybody helps me about any others, if they exist. I have searched a lot but I couldn't find any source that describes both topics. I would appreciate any relevant pointers.

• What is the initial value of the output variable Y (maybe zero?) – nekketsuuu Dec 22 '16 at 14:03
• What is so special about LBA? From the point of view of modern complexity, it is just an arbitrary complexity class. – Yuval Filmus Dec 22 '16 at 14:05
• @nekketsuuu , yes all variables at first are zero include y then within input X variables are assigned amount and local variables (Z) can be used in programs and assigned in it. – NedaHn Dec 22 '16 at 14:23