Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related

Question

Let $F$ be a field. Suppose we have a machine $T$ that works with words that are elements of $F$, for exmaple $F = \Bbb{Z}/2, \Bbb{Q}$ (using arbitrary precision arithmetic), or $\Bbb{Z}/p$ for a prime $p$. Empty memory is represented by the vector space $F^0 := 0$. If an algorithm addresses $n$ memory slots, that would be $F^n$. And of course memory can grow, and we represent that by embeddings and certain consistency relationships.

Define $C$ to be a computation category, or in other words objects of $C$ are $F^n$ for $n \geq 0$, and the morphisms of $C$ are precisely the set of all compositions of the following:

1. $S = S(n,i,j) : F^n \to F^n = x \mapsto $ swap entries $x_i$ and $x_j$.

2. $A = A(n,i,j) : F^n \to F^n = x \mapsto $ add $x_j$ to entry $x_i$.

3. $M = M(n,i,c) : F^n \to F^n = x \mapsto $ multiply entry $x_i$ by scalar $c \in F$.

4. $E = E(n,i) : F^n \to F^{n-1} = x \mapsto $ erase entry $x_i$ or $ = x \mapsto (x_1, .., x_{i-1}, x_{i+1}, .., x_n)$.

5. $I = I(n, j) : F^n \to F^{n+1} = x \mapsto $ insert a new entry $0$ right after entry $x_j$ or $ = x \mapsto (x_1, .., x_{j}, 0, x_{j+1},..,x_n)$ for $0 \leq j \leq n$.

6. $O = O(n,i,c) : F^n \to F^n = x \mapsto$ offset an etnry $x_i$ by $c \in F$ or $ x_i := x_i + c$.

for all $n \in \Bbb{N}$ and $1 \leq i \leq n$. These represent all atomic operations on a typical machine as well as all compositions of operations (applying one instruction at a time, right-to-left), except for integer arithmetic (unless we use $F = \Bbb{Q}$ in which case it's except for multiplication of two memory variables) loops, & conditionals. Clearly, however, if we add in the concept of loops & conditionals (or something encoding those) one could write an algorithm for adding integers represented say in binary ($F = \Bbb{Z}/2$).

Without axiom 6, all morphisms of $C$ are $F$-linear maps, while with 6 all morphisms are $F$-affine maps. In either case, without axiom 4 and with some slight modifications such as $c \neq 0$ and $i \neq j$ we get that all morphisms are invertible. If a ring $R$ is used in place of $F$, then the same holds as long as in 4 we restrict our "code" to only use units $c \in R^{\times}$ there.

So leave the axioms as they are, and the category $C$ holds all operations required for "things to be Turing-complete".

Now consider $T = \bigoplus_{n\geq 1} F^n$ to be the "tape space" which is sort of Turing-machine like in nature because $0$, which we'll call "blank" is the only symbol allowed to occur infinitely often at any given time. So if you wanted a binary representation of things and to be more Turing-like you should probably use $F = \Bbb{Z}/3$.

---

Now consider all endomorphisms of $T$ which can be constructed by changing each occurence of $F^n$ in the axioms with $T$.

Definition 1. One way to define a deterministic algorithm $f$, solving a problem $P : X \to Y$, in the computation category $C$ over $F$ is to define it to be a family of sequences (in $C$):

$$ M(x) = (M_n(x), f_n(x)) = (M_1 \xrightarrow{f_1} M_2 \xrightarrow{f_2} \dots) $$

indexed by $x \in X$, together with encode / decode maps $X \xrightarrow{g} \bigcup_{n\geq 0} F^n \xrightarrow{h} Y$, such that for all $x \in X$ we have that $h(f_{k(x)} \circ f_{k(x)-1} \circ \cdots \circ f_1(g(x))) = y$ for some $k(x) \in \Bbb{N}$, and such that each $f_i$ is a morphism from one of axioms 1 - 6.

---

But a more convenient way is to define it as a family of sequences:

$$ 0 \to M \xrightarrow{f_1} M \xrightarrow{f_2} M \xrightarrow{f_3} \cdots $$

of morphisms from the axiom list 1-4 but where $M$ is "big enough" to host the problem inputs / output encodings such as $M=T$ and 5 & 6 have been replaced with zeroing out and swapping entries.

---

Assume that $F = \Bbb{Z}$ for sake of argument.

Now under the latter setup, we have the concept of a while loop:

x2 = input
x1 = 0
while x2 != 0:
    x1 += x2
    x2 -= 1

encoded as:

$$ f(x) = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}x + \begin{pmatrix} 0 \\ -1 \end{pmatrix} $$ iterated $x_2$ times, or $$ P(n) = f^{n}\begin{pmatrix} 0 \\ n \end{pmatrix} $$ is the sum of the first $n$ natural numbers. Now, there is no $\dfrac{(n+1)n}{2}$ formula on our machine because there's no multiplication yet - it has to be defined first using the above "Turing-complete" set of axioms.

However, any time you have powering you have an efficient algorithm: Exponentiation by squaring.

---

In our example while-loop it was easy to calculate $n$ in it being just a component of our input vector. But usually in code it's difficult to compute how many times the loop will run precisely.

On the other hand, if $n$ is always increasing or always decreasing, meaning the value of $n$ a the $i$th iteration is $\lt$ the value of $n$ at the $i+1$th iteration (increasing), then squaring & checking will work efficiently.

For finite fields $F$ we need to define an ordering and be consistent with it. For $\Bbb{Z}, \Bbb{Q}$ etc, we define the ordering to be the usual ordered field, ring ordering.

---

Question. Does restricting our while-loop variable to be always increasing or always decreasing reduce the expressiveness of our collection of deterministic algorithms, meaning it would no longer be Turing-complete?

---

Feel free to answer in any programming language or math lingo you want. For instance can we solve the above issue by using a Python dictionary? I.e. it takes the loop variable $n$ modulo some small $m$ and maps it to the unrestricted loop variable's value. That's just a thought, and probably not sufficient to answer this.

---

Motivation. If the answer to the above is yes, then any algorithm that takes an exponential axiomatic steps to compute an answer can be done in close to $\log$ of that, meaning in polynomial-time. See: computational complexity of powering by squaring. This of course might help imply that P = NP.

---

To aid in understanding, a program computing an algorithm would end up looking something like:

$e\circ (f\circ (a\circ b^{x_{1} \neq 0})^{x_{3} \neq 0} \circ g)^{x_7 \neq 0} \circ d^4$

where $a,b,c,d,e, f,g$ are all examples of axioms 1-6, and the exponent of the form $x_i \neq 0$ means iterate until that condition is met, and a constant exponent will mean iterate a constant number of times.

So although a given algorithm may take exponential time to run, as long as there exists a program that takes up polynomial-space written like the above, you should be able to do powering-by-squaring & checking on each loop (as long as the answer to the above question is a yes). Thus reducing all exponential time algorithms logarithmically to polynomial-time. This argument is modulo some theory and math, but I have to keep things brief here.

Answer 1

While loops with increasing variables are enough for Turing completeness. For instance, it is enough to implement cellular automata, and cellular automata are Turing-complete. While loops with increasing variables are also enough to implement a Turing machine: you have an outer while loop that iterates over steps of the Turing machine, and you can implement a single step of the Turing machine by a left-to-right scan of the entire tape (which can be implemented with a while loop with an increasing variable).