# Is this system Turing complete?

I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.

I came up with the following idea:

The input is an array of $$N$$ integers. The genetic program consists of up to $$N$$ ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.

The ASTs can be arbitrary complex and consist only of four arithmetic operators ($$+$$, $$-$$, $$\times$$, $$/$$) and can operate on constants and fixed elements of the given array (no random access).

So for $$N=3$$, we have three ASTs, for example:

\begin{align*} a[0] &= a[0] + 1\\ a[1] &= a[0] + a[1]\\ a[2] &= a[0] \times 123 + a[1]\,. \end{align*}

The $$N$$ ASTs are executed one after another and this is repeated infinitely.

Now my question, is this Turing complete or will it fail to solve some kinds of problems common for an game AI?

• I removed all the AI and genetic programming tags that you used because there doesn't seem to be anything about those things in your question. It seems to be purely a question about computation theory: here's a model of computation; is it Turing-complete? – David Richerby Nov 4 '18 at 14:38
• Numbers are normal integers with fixed size. No I am not sure if I need turing completeness. I just want to make sure the language is not too limited, so it can never evolve to reach to to good-enough algorithm.. – codymanix Nov 4 '18 at 15:03
• If a program in your language can only use a bounded amount of memory (say, $64N$ bits), it is not Turing complete. If every program terminates, then it is not Turing complete (we need something like a potentially infinite loop or recursion). – chi Nov 4 '18 at 15:14
• As I wrote, the execution of all ASTs is repeated infinitely. – codymanix Nov 4 '18 at 15:39
• Ah, right. How do you determine that some value is the "output"? There is an "output array element", but that is overwritten at every step, so it can change. One could say "when element X stabilizes to a constant, then that's the output", but detecting that could not be feasible (it could be undecidable). – chi Nov 5 '18 at 19:26

You can probably use this to simulate register machines and, if you can do that, the system is Turing complete.

The setup is as follows.

• The machine has a sequence of names registers, each of which holds a non-negative integer.
• Program instructions are labelled with non-negative integers and execution starts with, say, instruction $$0$$;
• The three possible instructions are:
• halt;
• increment register $$R$$ and goto instruction $$I$$ (where $$R$$ and $$I$$ are integer constants);
• if register $$R$$ is zero, goto instruction $$I$$; else, decrement $$R$$ and goto instruction $$J$$ ($$R$$, $$I$$ and $$J$$ are constants).

For example, the following program adds the contents of registers $$0$$ and $$1$$ and halts with the sum in register $$0$$:

0. if R1=0, goto 2 else decrement R1 and goto 1
1. increment R0 and goto 0
2. HALT


My recollection from computation theory classes 20+ years ago is that you can simulate a Turing machine using a register machine with two registers (and certainly with some fixed number of registers). Proving this is long and tedious because you have to code up the tape and all manipulations of it as arithmetic operations and, heck, you even have to code up arithmetic operations such as addition, multiplication and exponentiation. Oh, and you'll probably have to be more careful than I was with my addition routine, because you'll probably want to do arithmetic on two values without destroying them both, which requires copying them to extra registers and then copying back.

You can simulate a two-register machine (i.e., a register machine with two registers) with $$n$$ instructions with your system as follows. Use two array cells to store the register values, and then probably one array value for each instruction, such that $$A[i]=1$$ if instruction $$i-2$$ is the next to be executed and $$A[i]=0$$, otherwise. Then executing the system with $$A=[x,y,1,0,\dots,0]$$ should simulate the register machine running with input $$x$$ in the first register and $$y$$ in the second. If there are $$n$$ instructions in the program, ASTs will look like this:

$$A[i]=(A[2]*v_0) + (A[3]*v_1) + ... + (A[n+2]*v_n)\,,$$

where $$v_j$$ is the value that should be stored in $$A[i]$$ if instruction $$j$$ is executed.

Note that all of this assumes that the array elements can hold unboundedly large numbers. If not, your system only has a finite number of states so cannot be Turing-complete. The simulation I have in mind only uses non-negative integer values in the arrays.

• I do not understand this. Could you elaborate more? Are v_j constants? What do you mean by "A[i]=1..A[i]=0, otherwise"? – codymanix Nov 7 '18 at 7:46
• The values $v_j$ will be values appropriate to the register being updated. For $i\in\{0,1\}$, these will be expressions of the form $A[i]\pm 1$; for $i>1$, they will be constants $0$ or $1$. "$A[i]=1$ if [condition] and $A[i]=0$, otherwise" means what it always means: if [condition] is true, then $A[i]=1$; if [condition] is not true, then $A[i]=0$. – David Richerby Nov 7 '18 at 8:31

If your $$/$$ operation is integer division (i.e. rounds towards 0, or towards the nearest integer, or in some other ways is confined to integers), and your array elements can grow arbitrarily large, your system is Turing-complete even without any form of branching (and without the ability to use a non-constant an array index, which could be used as a form of branching).

There's been investigation into this sort of system (arithmetic, but no branching) in various places (including on Stack Exchange); my own name for it is "Blindfolded Arithmetic" (i.e. you're doing sums, but you never get to look at the values you're working on because you don't have a conditional). A summary of many of the results is available here.

The basic idea behind the known solutions is to use integer division as a relational operator (if you're rounding towards 0, $$1 \over (x\times x)+1$$ is 1 if and only if $$x$$ is 0; and for positive $$a$$ and $$b$$, $$b+1 \over a+1$$ is 0 if and only if $$a$$ is larger than $$b$$), and multiplication to form conditionals (e.g. $$a+(c\times(b-a))$$ is $$a$$ if $$c$$ is 0, or $$b$$ if $$c$$ is 1).

Once you have relational operators and conditionals, all you need is a way to simulate unbounded storage. The normal method of doing this is to simulate stacks (which contain a finite number of possible elements, but can grow unboundedly large) using the digits of an array element to some base. For example, using base 10, you have 10 possible digits; pushing to the stack is multiplying by 10 and adding the new digit; popping the stack is a division and modulus ($$a$$ mod $$b$$ can be written as $$a-(b\times(a/b))$$). Two stacks allow you to simulate a tape, and then you can build a Turing machine. (You can even simulate halting, via division by zero.)

Without unbounded array elements, this can't be Turing-complete because it only has finitely many states. If your division works on the rationals rather than integers, I don't know what the computational class of the resulting language would be (there's no obvious way to prevent rounding errors accumulating, but there might be a subtle way to do so).