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.


1 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.