# 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? Nov 4, 2018 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.. Nov 4, 2018 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, 2018 at 15:14
• As I wrote, the execution of all ASTs is repeated infinitely. Nov 4, 2018 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, 2018 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"? Nov 7, 2018 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$. Nov 7, 2018 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).

• if you don't mind can I ask you some questions? have you written a self-interpreter for "Blindfolded Arithmetic" ? do you think a total self-interpreter is possible ? it seems to me since division by zero is the only way to halt, it is not possible to define an anti-total program therefore a total self-interpreter must be possible Dec 12, 2023 at 20:23
• Blindfolded Arithmetic is Turing-complete, so it can't be implemented by a total program. A self-interpreter would work by using Gödel numbering – encoding the program and the data it was operating on as numbers, then doing calculations on those numbers – and thus it would be possible for the self-interpreter to notice that the interpreted program was dividing by zero without actually having to do the division itself (division wouldn't have to be meta-circular). I haven't written a self-interpreter but there would be nothing conceputally difficult about it. Dec 13, 2023 at 21:08
• it seems to me that the diagonalization argument does not work for Blindfolded Arithmetic, assuming there is a total self-interpreter (or a halting decider) can you explain how do you diagonalize it ? thanks Dec 14, 2023 at 6:09
• There is not a total self-interpreter or a halting decider, because the language is Turing-complete and you cannot decide halting for Turing-complete languages. If you have a self-interpreter in general (not total), you can diagonalise using the standard technique of "simulate the execution of the halting decider on yourself and halt only if it doesn't halt" – there is nothing different here about Blindfolded Arithmetic compared to other Turing-complete languages. Dec 15, 2023 at 11:25
• my point is how do you prove that there is nothing different about Blindfolded arithmetic? do you believe that a "total [and turing complete] self-interpreter" and "a halting decider" are impossible (at least using current technologies) and no matter what programming language you came up with ? what if turing mahine is not the correct model of computation (because they allow to define contradiction) ? suppose I give you a halting decider for Blindfolded arithmetic written in Blindfolded arithmetic ... Dec 15, 2023 at 13:01