- A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

No constraints computer in CA

For general discussion about Conway's Game of Life.

No constraints computer in CA

Postby simsim314 » January 28th, 2019, 4:20 pm

Current computer architectures are limited in both, the command range and the input size. Practically computers are not limited to 64 bit integers, and can emulate big integers of any size. But we don't have "dynamic" architectures (not that I know of), where we can code new commands, and we are not limited only to N bits. In CA we can in general code addition of any two integers as big as they come, representing numbers by stream of gliders. This is in theory could be translated into electrical charges.

Lets place ourselves into CA with universal construction and computation. Imagine a decision tree (command tree) which can open and close gate by different gliders. So we can travel inside this tree redirecting the gates by gliders. Every command to the computer, starts from path inside this tree. Inside it there are "nodes" and there are "leaves". Each node is just redirecting the stream of gliders left or right, and every leaf can do something complex as the CA allows, which is basically everything.

So for example we start at the root: and say 1 will mean Add, and 0 will mean Multiply. Then we need a signal, when does one integer ends and the other begins. How would we do this if we only have two bits? We would code every digit with 0 prefix. So for example we have 7: 111 and we will code it (01)(01)(01). And to code the next digit we will use 1 prefix and then the same. So for example the code for adding 5 + 7 will look like this:
(1) - addition
(01)(00)(01) - 5
(1) - end of integer
(01)(01)(01) - 7
(1) - end of integer

So the code will look like: 101000110101001. This is a code that moves from the root to the adder leaf, and inside it it loads two integers 5 and 7 and they can be arbitrary large. How the result is returned is the next issue.

One of the things we should notice that many times one leaf would like to send command to another leaf. Like in every programming language we would like functions in our code to be able to call other functions in our code. This is why each "callable" leaf, needs the following structure:

Request: (helper command)(inputs for the leaf)(sender command) - this is how the information is passing from leaf to leaf inside the tree.

So for example if we would like to use addition inside Multiplication of 5 and 7 we would use the following code:
The input would be: 001000110101001 - we will have two integers 101 and 111.
Now I assume that we can define variables and make loops inside a leaf (but loop can also be a function inside the tree):

Create variable x = 0.
x = Add(x, 111) (here we call the root with command, 0, (x, 7), 1 and wait)
call root ("command print" x)

Now in order to call some other function, we need to have an inherent capability of every leaf to send message to the root. How this is done is beyond the scope of this issue, but in practice in CAs this is doable. So for example if someone asks some function to calculate something, it sends request to the root, and each smart enough leaf will know to send back to the root the result stream of the type:

Result: (sender command)(results of calculation)

As the sender will wait for the result, after the result will come, this is up to the sender leaf to know what to do with it. We just make sure that the command tree design is supporting this option.

Some example of problem that can rise from this design is recursion. If function is in the middle of and execution and it calls itself to make a calculation, or it calls some other function that calls the first one, this can collapse the system. So this is not a mistake free system in any way. This is up to the designers of the leafs to make sure that when they call some other function they know enough of what they are doing (like designing a stack of data for recursion). We can have some design patterns automated for this purpose, yet this is in the hands of the leaf designers.

Now the best part of this idea can exist only in CA with universal construction. Because we can have version control and inherent part of our computer. The only thing we need to add, is a code that creates and destroys components inside this computer. So when we call a code with some version, the version loads the code that creates the whole computer. Each new version of the computer is coded inside a universal constructor. Each leaf and node of the command tree, can first be rebuilt from version 0 to version N, and then some specific code of version N can run. Every new version of the computer say version N + 1, is deleting some of the leafs replacing them by nodes, and moving the leafs downwards the tree stream (see note 3 for improved design).

I wonder have anyone had or heard of this idea ? Or maybe someone implemented it on some emulator? I think FPGA guys should be able to think about this stuff. I was also thinking of implementing it in GeminoidParticles rule where there are reflections, duplications, and construction of any static unit but not particles - this reflects nicelly the distinction between the signal and the hardware, which usually not that clear in CAs as in reality.

Note There is no need to differentiate the code and the execution. The execution is just another leaf which start to read some tape, and this is where it all originates. Not in the root but in this leaf. This leaf is somewhat special as it takes the first argument how many bits to read, then it reads those bits and sends them to the root node. And from this point onwards everything is as usual. We just need to start the execution from somewhere.

Note 2 Obviously something more esoteric in CA which is impossible to make in physical computer like calling a leaf with universal constructor, and generate a stream that makes another temporary leaf is also an option.

Note 3 Although the versions are controllable true back compatibility is an issue. But one can notice that every specific node can be only one of two things. A leaf or a node. We can make sure that each leaf is also node friendly, and we can run at first some version generator, that will not create everything from scratch, but will define the active component to be a leaf or a node. Inside each "node friendly leaf" there will a version when it became a node from a leaf, and if the current version is higher then a node will be activated. This is some sort of initialization that can be done at first as part of design pattern of the tree. Each version will need to have a special node which will return result command to the root - call the execution node once again the version is now initialized.

Note 4 As I mentioned earlier each node is a gate which redirects the rest of the stream. One important issue should be managed in the command tree, when the command is happy and understands the input finished to be loaded, it needs to reinitialize the gate. This property is part of the node design - each node is sending its parent node everything is finished loading reinitialize back into the neutral state.
User avatar
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: No constraints computer in CA

Postby simsim314 » January 29th, 2019, 7:21 am

As part of the computer thinking I was wondering about the optimal bit efficient representation of big ints.So now we have 50% efficiency using 0 prefix. If we use 64 bit computer, we can have 63 efficient bits. Thus we can reach N * (1 - epsilon). We will still lose N * epsilon bits, for epsilon arbitrary small but this is still O(N) lose. For large Ns is not fun. And we can't always assume we can adapt the epsilon by N.

Lets assume we have a stream of 0,1 of length N. We need to know where the integer is ending and we know it has less than N bits. We still have N options to divide the bits. I mean we need to translate 01010101111 to some sort of (010110)(1111). There are N options to do this separation. To code those N options we need LogN bits. So we can say lets define the length first with LogN bits, and then we will use N. How do we code LogN? lets say with 2 bits per bit paradigm. So in order to code 14: 1110 instead of using (01)(01)(01)(00)(1) we will first code the length which is 4 (100) in this way (01)(00)(00)1 and then we will use the length to know where to cut. So for instance 14 will be coded: 01000011110 -> (01)(00)(00)1 + 1110. The overhead here is that we still use N + 2LogN. But for logN itself we can use the same trick. Thus we will get us to N + LogN + 2LogLogN. One also should notice that we can make machine that will interpret N + 2LogN, and N + LogN + 2LogLogN but we still don't have a machine for arbitrary large length of Logs.

Notice that we use length to define the container size. So when we read a number we can have two of the following: 1. The number itself. 2. It might be a container size for the next number. This can be coded in another bit which is read after the number. So for example lets take 79 = 1001111. It's length is 7 = 111 it's length is 3 which is 11, Its length is two which is 10, and we stuck here, there is no way to reduce it to single bit. So lets start from two bits hard coded. 00 = 0, 01 = 1, 10 = 2, 11 = 3. Now we add another bit to check out if this is a container or a number. We would have 0 - number, 1 - container. So to code 79 we will have - (11)(1)(111)(1)(1001111)(0).

I've written a python code to show the idea. I've modified a little bit the coding policy in the low integer case. I probably still lose some bit here or there, But the claim is that the efficiency of this algorithm is optimal up to O(1) for arbitrary large integers. With very small overhead (maybe two-four bits are lost in the process).

#Bit efficient binary representation of any arbitrary size integer

def code_binary(x, is_number = True):
    result = ""
    #small numbers will start with 0 prefix, reduced length from larger numbers must be >= 3
    if x < 4 and is_number:
        if x < 2:
            return "00{0:b}".format(x)
        return "0{0:b}".format(x)
    #now we assume our number >= 4 and its length >= 3.
    #We use 3 next bits to define a number and to define if it's a number of length.
    if x < 8:
        result = "{0:b}".format(x)
        if is_number:
            return result + "0"
            return result + "1"
    bin = "{0:b}".format(x)
    y = len(bin)
    if is_number:
        return code_binary(y, False) + bin + "0"
        return code_binary(y, False) + bin + "1"
def binary_interpret(bin):
    if bin[0] == 0:
        return (int(bin[1:3], 2), bin[3:])
    start_idx = 0
    length = 3
    while True:
        x = int(bin[(start_idx):(start_idx + length)], 2)
        if bin[start_idx + length] == '0':
            return (x, bin[(start_idx + length + 1):])

        start_idx = start_idx + length + 1
        length = x

for i in range(1000):
    print i, code_binary(i)

x = 12345678901234567890
y = 11111111111111111111
bins = code_binary(x) + code_binary(y)
print bins
x1, bins = binary_interpret(bins)
y1, bins = binary_interpret(bins)

print x1, y1

EDIT I want to compute efficiency and present some sort of paradox involved here.

For starters Lets define Log_k(x) = Log(Log(Log...(x))) k times. We are looking for first k for arbitrary N such than log_k(N)<=3. Now notice we have been coding this k in very inefficient way, we used the number of 1s to represent k. For example to represent 5 we used 111110. This is obviously inefficient. We at least could represent it in binary format with 2 log(k) bits. The paradox here is that in order to represent k more efficiently we are stuck again in the same loop. We're looking for optimal representation of k now. And k is much smaller than N. So lets say we will move the binary representation of k as the first number to represent. And writing 15 times 1, we will write 1111 = (01)(01)(01)(01)1 = 010101011. Which is shorter. The problem arises that our interpreter is becoming more and more complex once again like in case of the Logs. If N requires to code k first then k requires to code some other k1 first. Now we get once again some ki, and we need to define their length. If we don't want the complexity of our interpretation unit to rise to infinity, we need to cut this infinite loop somewhere. But notice there would always be some more efficient bit representation for arbitrary large ints. But we could approach optimal representation. For example lets use current representation to represent k but then we will avoid k times one representation. So we got a new representation now. Lets use it to represent k it will cause k1 to appear, this k1 will not be represented optimally. There is still something in this approach which need sometimes to represent some subset of integers in somewhat sub optimal way.

For any practical purposes I think the logarithmic scale posted previously is enough. The overhead for each wasted bit is exponentially growing.

Another question is it possible to prove mathematically that there is no optimal representation of arbitrary large integers, and that every computer what will try to represent integers more efficiently will need to increase in complexity?
User avatar
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: No constraints computer in CA

Postby calcyman » January 29th, 2019, 9:58 am

What you're describing is known as a 'universal code', and I think you've reinvented the Elias gamma code and Elias delta code in the process.

If you apply this idea recursively, the limit is called the Elias omega code:

The 'optimality' of a universal code depends on the probability distribution of the integers you're trying to compress.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
Posts: 2025
Joined: June 1st, 2009, 4:32 pm

Re: No constraints computer in CA

Postby simsim314 » January 29th, 2019, 11:57 am

calcyman wrote:What you're describing is known as a 'universal code', and I think you've reinvented the Elias gamma code and Elias delta code in the process.

Thx, Nice to know!

But have you heard about the computational paradigm from the first message? It's kinda allows to build code like geometry. From assembly to high level programming in the same basic framework of arbitrary length command pointers (obviously we're not living in CA so it's not trivial to implement in physical computers but) as a paradigm?
User avatar
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 1 guest