This is the thirty ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to simulate non-deterministic Turing machine using ILP. Let’s begin.

Idea

What is a Turing machine? Conceptually it is a simple computer capable of reading and writing symbols on an endless tape following specified algorithm. A bit more formally, Turing machine has a transition function which accepts current state and a symbol on a tape, and returns new symbol to be written on a tape, direction where to move (left or right), and new state. Non-deterministic machine has a “function” which might have multiple results for the same input.

We are going to simulate Turing machine using ILP. We are going to confine ourselves to finite tape and finite number of steps, so our machine will not be very powerful.

Code

Let’s start with some code:

This code checks whether word specified on a tape is a palindrome. It uses three symbols: aSymbol representing letter “A”, bSymbol for letter “B”, and emptySymbol for empty space, all of them defined in lines 30-32. Our tape has five elements (this is enough for our requirements). We assume that our word is stored in positions 1-3, positions 0 and 4 are empty.

Idea of algorithm is simple: we start on left side with empty symbol. Next, we move to the right in search for first non-empty symbol. When we find it, we move on to right side to first empty symbol, and next we move back one step left and verify if symbols match. In that case — we move to the last empty symbol from the left and do the same again. In other case, the word is not a palindrome.

States are defined in lines 21-28. Their names should be rather straightforward. Next, in lines 36-38 we define position and possible directions.

In lines 40-60 we define transition function:

1. Line 42 — if we are in initial state and see empty symbol, than it means, that word is empty (by assumptions) — we don’t change symbol, move on the right (basically anywhere), and signal success.
2. Line 43 — if we are in initial state and see letter “A”, we remember that we will be looking for matching letter “A” and currently want to move to the right side. We also clear symbol and move right.
3. Line 44 — as previously but with letter “A”.
4. Line 45 — we are going to the right side and we spot empty symbol — this means that we reached right side. We change state to find matching letter “A”, clear symbol, and move left.
5. Line 46 — we are going to the right side and we spot letter “A” — we don’t change it and continue movement.
6. Line 47 — the same as before but with letter “B”.
7. Lines 48-50 — the same as three previous rules, but we want to match letter “B” after reaching right side.
8. Line 51 — we are moving left to match letter “A” and we spot empty symbol — this means that we previously cleared last letter of a word and now whole tape is empty. Our word is a palindrome so we signal success.
9. Line 52 — we matched letter “A”. We now want to move to the left side of a word, clear letter, and move left.
10. Line 53 — we spotted letter “B” when trying to match “A” — our word is not a palindrome, we signal failure.
11. Lines 54-56 — the same as three previous rules, but for letter “B”.
12. Line 57 — we are going to the left and we spot empty symbol — this means, that we reached left side of a word. We are back in initial state, clear letter and move right.
13. Line 58 — we are moving left and we spot letter “A” — we simply move on.
14. Line 59 — the same for letter “B”.

Ok, this is our transition function. Now let’s move to implementation.

In line 62 we specify that we will have at most 12 iterations — this should be enough for specified case. This value should be tuned to be high enough to make sure that our algorithm stop (you need to solve the halting problem on your own).

In line 65 we execute our machine. In line 67 we add dummy goal, next we solve the problem, and finally we check the status of our machine. We simply print whether the final state signals failure or success.

Machine implementation

We have our problem defined, let’s now examine machine implementation.

In line 82 we start a loop. We will spin at most maxIterations times. We simply emulate whole machine.

In line 84 we extract symbol using ArrayGet operation defined in previous post of this series.

Next, we want to find matching rule in transition function. Since we have non-deterministic Turing machine, we start with defining temporary variable (line 85) whether we already matched anything in this loop iteration, or in other words, whether we already made a choice. Having correct transition table would be perfect, however, we probably cannot assume that one provided by the user is absolutely correct, thus in line 86 we define another variable stating whether we had any potentially matching rule.

Loop 87-109 iterates through all rules in the transition table.

In lines 89-92 we check whether we can follow current rule or not. We compare current state and symbol with these specified in transition table. We also check whether isMatch is not true which would mean that we already chose different rule.

Next, in line 94 we remember if any rule matched. If isMatch is true, we deduce that we had at least one matching rule in transition table.

Next, in line 95 we make a choice whether we use this rule or not. We simply create boolean flag and leave the rest to the solver — it will decide. This is the non-deterministic part.

In line 96 we update our isMatch indicator — we take solver’s decision into account.

In line 97 we update state, whether we chose any rule in this machine state with given symbol.

It is worth noting here that if we remove lines 95-96, we end up with deterministic Turing machine!

Lines 99-110 simply update machine variables. In line 99 we change state only if we use current rule. In lines 101-107 we update symbol on a tape. Next, in line 110 we move to the left or to the right, depending on the chosen rule.

Finally, in line 112 we add final constraint — we require that if we had any potential match for given symbol and state, we follow one matching rule.

Summary

We started our adventure long time ago. We saw how to implement binary logic, how to multiply variables and perform other arithmetic operations. We implemented multiple riddles and solved various problems using ILP. We implemented imperative constructs, sorted numbers, compared vectors. We created imperative data structure. Today we see that we can simulate non-deterministic Turing machine. It is slow, it uses lots of variables, it has multiple constraints on variables’ values and allowed operations. But it is possible. If we could utilize infinite memory and have very long time, we could in theory represent any finite algorithm using this approach. Is it useful? Probably not. Is it interesting? Well, since you have reached so far…

In next part we are going to solve Rubik’s cube.