On Turing Completeness of LESSTweet
Continuing with my earlier post “LESS is More” about how different it is to write a simple Fibonacci program in LESS, I wanted to really understand the main differences of LESS from more general purpose programming languages like Java, C++ etc. Also, whether this language is as powerful as these other general purpose languages, or in other words, is it Turing complete? There are some key differences which become apparent after some use of this language. For example, One cannot define methods which return a value, instead, variables defined by methods become available to calling method. These variables can then be used by callee to return values to caller.
A variable in a given scope can hold only one value. This is similar to some functional languages where all variables are immutable. This also applies to variables which become available from callee. Since, user defined methods also return value via variables, a side effect of this limitation is that one cannot call a user defined function more than once with different arguments. If you did that, then there would be no way to access value of returned variable from second call. This is because as value from second call will not be able to override it.
Apart from above language supports recursion, which makes it possible to write infinite loops. Ability to write infinite loops is one of the differentiators of turing complete languages. As explained by Douglas Hofstadter that a language without ability to express non terminating loops is definitely not Turing complete as programs written in such a language are always halting and therefore do not suffer from halting problem, which is one of the characteristic of turing complete languages. But can we still say that language with given limitations turing complete? In order to prove this we would have to emulate either turing machine or any other equivalent model of computation using this language. One such model is Rule 110. Rule 110 is a cellular automaton, it has been proven that it is turing complete, so if we can implement Rule 110 in LESS we can be sure that LESS is also at least as powerful as a turing machine. But what does it mean to simulate Rule 110 cellular automata(RCA from here on)? Simulating Rule 110 means that we would have to define a function is LESS which when given an initial configuration of RCA and a number, representing number of generations or steps, will give final state of RCA after given number of generations of RCA.
Input Encoding and data structure
Before we begin, we need to decide encoding for the state of RCA. For RCA we just need some way to store a sequence of zeros and ones. We can use string to store zeros and once but it seems that there is no way to access individual characters of string in LESS. Other option seems to be lists but it seems there is no way to modify or even append elements to a given list. For example, if we try to append an element to a given list, it actually creates a new list such that first element is the element we appended but the second element points to entire list and length of this new list comes out to be two, no matter how large the original list was. So, it seems there is no way to manipulate/access a sequence of zero and ones. But all hope is not lost and it seems we can create a new data structure using these native lists. This new data structure is based on the idea that when we create a native list of two variables, each of which can be a list, it creates a new list of length two such that each element points to two variables. We can use this to create LISP like lists, in which list consists of pair objects, each object has two elements (first and second), first element points to the element in the list, and second element points to remaining list. There is also a null element, the second element of last pair points to this null element.
For our purpose we can chose “-1” as the null element since we have to store only zeros and ones in the list. Since this list is not a native data structure we would have to write certain methods for working with this list. Before we start writing code for these methods there is a minute detail, a convention, that we are going to follow in this post. As there is no way to return values from functions in LESS and value has to be returned as a variable, we can follow a naming convention for these variables that are used to return values. So, in this post we are going to follow this convention that a function named “foo” will return its result in a variable named “foo_res”, similarly, a function named “foo_bar” will return its result in “foo_bar_res” variable.
With these conventions lets write our first method. This method converts native space separated list of zeros and ones to our LISP like lists.
This method takes @nlist variable as an argument which is a native LESS list. It then defines a recursive routine “-“. This routine is used to iterate over @nlist. There are two definitions of “-“ method. First one takes first argument @i which is position in @nlist that is to be processed by this call, second argument @acc is an accumulator, it is used to build our list. This definition also has a guard condition such that it will be executed only when @i is greater than zero. This definition recursively calls “-“. It passes a decremented value of @i and in the second argument we use “extract” built-in function to take value of @nlist at @i position and combine it with @acc. This expression creates a new pair, such that first element is the value read from @nlist and second element points to whatever is in the @acc. The second definition of “-“ is executed only when first argument is “0”, this happens when we have already traversed all of the list. At this point @acc contains our list, we simply create variable “define_list_res” and set its value equal to @acc. This variable here is being used to return the value. Finally we call the “-“ with no arguments. By default value of its first argument will be set to length of @nlist and value @acc will be set to -1. To see this method in action, add following lines to the script and then run it using LESS
This should print our created list. Our list is a nested data structure but LESS prints it as flat list. This can be confirmed as length of the list is printed as 2. This is because structure of our list is composed of multiple lists, each of length two. Something like [0, [0 , [0 ,[0 , [1 , [1 , -1] ] ] ] ] ]
Now lets define few more functions for working with these lists.
- list_len function to calculate length of the list.
- tail_list to find tail of the list after skipping given number of elements
- reverse_list function to reverse the input list
I will not go into detail to explain these methods. All these methods use recursion to iterate of input list. tail_list function probably deserves some explanation in that, it skips @num_skips number of elements in the list and returns the remaining list. In previous section when we used native “length” method to find length of our list, it returned 2. Now we can use this new method to find actual length. Replace .print_result block with following and again run using LESS compiler
It should now print following output
Now that we have basic set of functions done, we can start writing actual program. For Rule 110 we first need to write a function which given state of then cell and its neighbouring cells, outputs final value of the cell after one generation. Such a function can be return as follows.
This is a simple function, a call to .rule_110(1,1,0) will return 1 as value of @rule_110_res variable and call to .rule_110(1,0,0) will return 0.
Calculating one generation of cellular automaton
Now lets write the function which given state of the machine, outputs state after next generation. Our cellular automaton consists of a sequence of cells. Each cell can be in either of the two states, zero or one. Therefore, state of the machine is represented as a sequence of zeros and ones.
In short this function takes as input the current state of the machine. It iterates of each element of that list, it creates triplets of element containing previous element, current element, and next element. It passes these triplets to rule_110 function to calculate next state of the current cell. These states are combined in @acc to form next state of the machine or next generation. It handles two edge cases, first when @pos, which points to current position in @machine_state being processed, is equal to 1 and second, when it is equal to length of the @machine_state. These two cases represent the two ends of the list representing @machine_state. When @pos is 1 it considers left neighbour as 0 and when @pos is @machine_state_len it considers right neighbour as 0. The final list created this way happens to be actually the reverse of the next generation. This happens because we process elements from 1 to end of the machine state but append result in our list from backward to front. This is because of a limitation of our list data structure, in which, only way to traverse it is to from front to backward and only way to create it is from backward to front. Nevertheless, we remedy this by using reverse_list function in the end, to reverse the resulting list.
Completing the Simulation
Now lets write final method which computes final state of machine after given number of generations.
This method simply calls apply_rule110 method @cycle times, passing result of previous calls to it as its argument. Writing this function is critical to this proof. As simulation of only finite number of steps does not constitute as proof. Since, with this method we can simulate arbitrary number of generations. Memory and time are the only limitations. You can test this method by adding following
This should print following, which is the final state of automaton after 29 generations
With above it seems that LESS is indeed a turing complete language. There are only some limitations which make it hard to do such simulation and probably other general purpose tasks. For example, if there were library routine to append elements to native list, we would not have to roll out our own list. Similarly, a mechanism to define methods similar to built-in ones, which can return values would also make it easier to use this language for more general purpose uses.