Image not available

1080x581

Screenshot_202407....jpg

🧵 Arithmetic-only version of Conway's Game of Life

Anonymous No. 16285583

who here brainhead enough to fix this desmos error?

https://www.desmos.com/calculator/wex0ezcc9u

bonus: simplify the entire thing

Anonymous No. 16285593

>>16285583
First I would like to know what “Arithmetic only version of Conway Game of Life” is. What are the cells and what are the rules?

Anonymous No. 16285600

Not sure exactly how you could represent the rules as a summation. Please provide more details of how you got to this point.

Anonymous No. 16285616

>>16285600
Well you can use goedels trick to codify programs.
If you can codify a program you can codify a Turing machine that executes a Conway Game of Life.
You can express the partially computable program snapshot of the state of the program in "n discrete execution steps".
Now I don't know what the fuck are all those numbers, probably something like that in a more convoluted way.

Anonymous No. 16285632

>>16285583
in f(n) s seems to be used without definition
since you've used a floor function around it, i assume s is not strictly an integer value

Anonymous No. 16285636

>>16285632
nevermind, i realize it needs to be read bottom to top in order to make sense

Anonymous No. 16285646

>>16285616
>Well you can use goedels trick to codify programs.
What exactly is Godel's trick? I haven't heard of this nor have any internet searches yielded hits.
I'm unsure if you are a total schizo or next level brilliant. Bonus points for originality if this is bait.

Anonymous No. 16285676

>>16285646
https://en.wikipedia.org/wiki/G%C3%B6del_numbering

Given a set of instructions.
A program is a list of instructions.
A program execution is the program plus the execution state codified in some way.
You use goeddel numbers to codify instructions, programs and program executions.
You can use this to write a program that execute programs (the universal program).
Now the programs you write have a natural number representation.
Not only that but every state of a program execution is represented by a natural number.
So now every natural number represents some program in some execution state.

This means that given a programming instruction set and a given codification you can say "The conway game of life, with a board of 10 x 10, with this intial state in the execution state of the simulation n".

So with some autism you can probably express the same thing as a summation or a maximization.

Anonymous No. 16285718

>>16285676
To answer your original question the error in Desmos is simply that you're reusing the symbol i. You've defined i as a function then reuse that symbol as an input to function m(i,j). I don't know the rules Desmos operates by but this is the most obvious problem to me.

Your approach is somewhat innovative and intriguing. I have a background in both math and CS and never seen someone use Godel Numbering for this purpose. Of course it's theoretically possible since as you said a computer program and its states are enumerable. It's just that I have never seen someone make a serious attempt at doing so. It would be very cumbersome for all but the most trivial of programs. Even CGOL with its simple rules might be too much. It would be interested in knowing more about how you constructed these functions, should you be inclined to share.

Image not available

4080x2296

20240715_201833.jpg

Anonymous No. 16285722

>>16285600
does this help?
basically, s=... is where the von Neumann sumation happens, f(n) is where s is used to compute the output for the nth cell for next generation.
note: I am not working in base 2, but in base 10, so in order to print the cells and board you need to 1:) convert the base 10 f(n) into base 2, then add a new line character every p binary digits.
>>16285636
i tried shuffling the equatio order around it didnt help

btw, I can also post the python code for this if you want.
typically, a python implementation uses three if then statements to fulfill the GoL rule, but mine doesn't. it uses pure arithmetic.

Anonymous No. 16285735

>>16285718
you seem hooked so here:

import random

d=31
dd=d**2
obint=random.randint(0,2**dd)

obbin=bin(obint+2**(dd-1))[2:]
for i in range(d):
print(obbin[d*i:d*(i+1)])
print()

while True:
nbint=0
for n in range(1,1+dd):
s= -((obint%(2**n))//(2**(n-1)))

for a in range(-1,2):
for b in range(-1,2):
s=s+ int( (obint%(2**(((n-n//d*d+a)%d)+(((n//d)+b)%d*d)))) // (2**(((n-n//d*d+a)%d) + (n//d+b)%d*d -1)) )
nbint=nbint+ ((1-((s%(2**3))//(2**2)))*((s%(2**2))//(2**1)) * ((s%(2**1))+(((obint%(2**n))//(2**(n-1))))-(s%(2**1))*(((obint%(2**n))//(2**(n-1))))))*int(2**(n-1))
obint=nbint

#print(obint)
obbin=bin(obint+int(2**(dd)))[2:]
nobbin=""
for i in range(d**2):
nobbin=nobbin+obbin[i]*2
for i in range(2*d):
print(nobbin[2*d*i:2*d*(i+1)])
#print()

Anonymous No. 16285747

>>16285718
>>16285722
Also more fundamentally is that f and s are defined in terms of each other. Without the ability to specify a function signature without a body (as in C for example) this won't work.

In a simplified example you're trying to do
f = s
s = f

If you imagine a simple compiler or interpreter is scanning this line by line, one it gets to the definition of f it will see an unknown symbol s. If you try to define s first then you don't have a definition of f yet.

If you can find a way to break up these functions so they aren't linked recursively to each other it will be easier for a tool like Desmos to process it.

Anonymous No. 16285758

>>16285747
Actually I see now that you're using S as a text macro. It's not a function it's a symbol that should be replaced verbatim with its definition. I assume to f more readable.

To make this work in Desmos you'd have to read their documentation or maybe post on their forum if they have one. This probably isn't something most people are doing so it would be hard to get support on it.

Anonymous No. 16285766

>>16285722
>Jesus is Lord
Based schizo

Anonymous No. 16285885

>>16285758
yes, it's for readability
I guess, for this to work in desmos, I'll just
have to lump all the equations into a single equation
will post again if I get to a library computer before this thread is heleted my mohs
>>16285766
there are 66 books in the Bible

Anonymous No. 16285892

btw, the motivation for this project is to come up with a branchless algorithm for conway's game of life
it has the potential to be much faster than existing CGoL algorithms, but only if the arithmetic can be simplified down from its current state
during testing, this implementation is at least 2x slower than a basic imprementation (that uses three if then statements, and lint manipulation)
the reason is because python does if then statements very quickly, on par with integer manipulation
also, after the arithmetic is simplified (if it can be), then I will swap out the modulus operators for much faster bit manipulation and do the whole thing in base 2. the base 10 arithmetic is purely to explore a possible analysis of siplifying the math down to some form that is unforseen in base 2

tldr: I need a mathematician

Anonymous No. 16285895

>>16285885
Good luck. Post back if you get it to work I'm interested in what it will look like. Also I think you can get rid of most of your usage of floor to simplify. Like there is no point to floor(n choose m) since it will always be an integer.

Anonymous No. 16285898

>>16285895
those aren't choose operators
for some reason the screen shot didn't catch the divide line that's supposed to be there
I included the desmos link, so see for yourself
(I took the screen shot on my phone since the library computer does allow screen shots)
it's an issue caused by zooming out that I didn't catch before posting

please make a proper screenshot yourself

Image not available

4080x3060

20240717_220018.jpg

Anonymous No. 16285904

>>16285895
this is how it's supposed to look

Anonymous No. 16285969

>>16285735
video of code running in python
https://youtube.com/shorts/JEY_immMeus

Anonymous No. 16285974

>>16285969
bro you're coding on a phone
the actual fuck

Anonymous No. 16285996

>>16285718
>Your approach is somewhat innovative and intriguing.
Are you serious or just trolling me?
I mean, isn't it standard comp sci computability stuff?

Anonymous No. 16286000

>>16285718
I mean it is a theoretical result, you can't have an interpreter running those programs because the codification would produce ridiculous gigantic numbers with extremely big primes.
But the point is that you can theoretically express programs and program executions as number codifications.

That's how at least I learned it alongside the meme turing machines.

Anonymous No. 16286003

>>16286000
>>16285718

First you define the S language.
1) A infinite numerable set X1, ..., Xn called "input variables"
2) A infinite numerable set Z1, ..., Zn called "auxiliary variables"
3) A symbol Y called "output variable"
4) A infinite numerable set A1, B1, C1, D1, ..., An, Bn, Cn, Dn of elements called "labels"

The S language have 4 instructions:

1) V <- V +1
2) V <- V-1
3) IF V =/= 0 GOTO L
Where V is variable X,Z or Y and L is a label.
4) A special instruction V<-V that "does nothing" (this is usefull to simplify some edge cases when you codify the S programs)

A "labeled instruction" is an instruction that starts with a [L] specifying a label


For example a program in S

P1:
[A1] X1 <- X1 - 1
Y <- Y+1
IF X1 =/= 0 GO TO A

This program computes P1: N0->N0
P1(x1) = x1 if x1 > 0
1 if x1 = 0


- You can (insert theory) show that S is equivalent to a turing machine
- So you can code with S every basic function that you want, for example sum, multiplication, conditionals, and even logical conditionals.
You can even express minimization.

Anonymous No. 16286005

>>16286003

- Now a program P is a numbered set of instructions I1, ..., In
- A program execution is a Program plus a map representing the current state of the program indicating the value of all the variables of the program
for example (X1=0, Y=7, Z3=5) it also defines the current instruction to execute i.
- With this you can define the "snapshot" of an execution
- You can also formally define the semantics of the program execution you can specify how to derive s' from state s (s->s') given the current
state of the variables and the current instruction.


For codification you first start codifying ordered pairs

You define the primitive recursive function <x,y> = 2^x(2*y+1)"-"1
OBS = x"-"y = x-y if x>=y
0 if not

Proposition: There is an unique solution <x,y> = z (proof, 4you)

You can define observers left, right, for the ordered pair
l(z=<x,y>)=x
r(z=<x,y>)=y

The observers are also primitive recursive functions (proof, 4you)


You can also codify sequences
This is where the godel numbering plays.
You can basically say that a1, ..., an is [a1, ..., an] = Prod_{i=1}^{n} p_i^a_i where p_i is the i-ith prime number.

So [1, 3, 3, 2, 2] = 2^1 * 3^3 * 5^3 * 7^2 * 11^2 = 40020750.
OBS: To avoid the fact that [a1,...,an] = [a1,...,an, 0,...,0] you set a condition on the S language that the last instuction of the program can't be
the "do nothing" instruction.

You can define the observers (also primitive recursive)
- x[i] = a_i
- |x| = n

Anonymous No. 16286007

>>16285996
Not really. Godel number is undergrad level CS. Using it to implement CGOL is definitely not.

Anonymous No. 16286014

>>16286005

So you have
1) The definition of your S language (that is turing computable)
2) The semantics of computation (adding to variables or jumping the pointer, also computable)
3) A way to codify ordered pairs and sequences (primitive recursive, ergo computable)

You can use all of that to codify programs and program executions.
For example you can codify an instruction I doing the following.
First you set an order for variables and labels:
- Y, X1, Z1, X2, Z2, ...
- A1, B1, C1, D1, A2, B2, C2 ....


- #(V) specifies the index (index start from 1) in the ordered sequence of the variables
- #(L) specifies the same for the labels

- To codify the instruction I you simply do
#(I) = <a, <b, c>>

where
1) a=#(L) or 0 if the instruction doesn't have a label
2) If the variable referenced in the instruction I is indexed at i then c = #(V) -1 = i-1
3) If the instruction b is
3.1) V<-V then b = 0
3.2) V<-V+1 then b=1
3.3) V<-V-1 then b=2
3.4) IF V =/= 0 GOTO L then b=#(L)+2

For example
#([A1] X X + 1) = ⟨1,⟨1, 1⟩⟩ = ⟨1, 5⟩ = 21
Every natural number representes an unique instruction

Now a program P is a finite list of instructions I1,...,Ik and is codified as
#(P) = [#(I1), ..., #(Ik)] -1


- There you have your program codified.
- In the same way you codified the program you can codify the state of the program execution.
- Now you have a single number that representes a program and the current state of the program codified as a single number
- You can write a program in S that is an interpreter of S, you can implement the S semantics in S.

Anonymous No. 16286015

>>16286014
Given all of that you can in theory also codify the parameters of a Conway game of life, the board, the initial state and the execution step of the simulation.

And you can use all of that to represent your Conway Game of life as a fancy product and summation of bullshit.

Anonymous No. 16286375

How does it apply rationally?

Anonymous No. 16286663

good luck

Anonymous No. 16287419

>>16285583
https://www.desmos.com/calculator/oyvp7tuhqn
Is this what you were looking for?

Anonymous No. 16287495

>>16287419
interesting
I'll have to spend some time parsing it but it looks like you simplified it a bit?
in addition to getting it all connected together without error

what's the 1/1440 ?

it'll take me some time to transcribe your formulation into python to check it

Anonymous No. 16287532

>>16287495
I started from scratch. 1440 normalizes the polynomial, I need to select for the specific rule conditions individually. Having so many terms makes the odd one out very large. If I used trig functions, it could be a little nicer.

Image not available

1080x2408

Screenshot_202407....jpg

Anonymous No. 16287737

>>16287532
>>16287532
I just realized playing s shows the glider moving
you did it!
you even did the Cartesian plotting!

Anonymous No. 16287757

>>16287737
Thank you! :)
I hope the formulas are sufficiently readable.

B contains the array for the whole board, c will reference a specific cell, and K will count the cells in the kernel.

Anonymous No. 16287807

>>16287737
amazing. congrats on getting that to work.

Anonymous No. 16287835

ITT: A rogue AI gets help from 4chan on constructing an alternate universe simulated in an internet graphing calculator

Anonymous No. 16288305

>>16287419
Wait what is this? I had assumed OP was literally a schizo but it seems you understood what he was talking about. What is “arithmetic game of life”?

Anonymous No. 16288457

>>16288305
>>16285892
The point is that if you can use only arithmetic operations, the code would have no branches, and CPUs try and predict ahead what the program will do next and get started early, so if the program branches in a direction that the CPU does not anticipate then the time spent on calculations is wasted and it slows down.

Anonymous No. 16288512

>>16288457
that is an improvement, yes, but the real improvement is where redundant calls are simplified down to one call.
in CGoL, the typical alg is where you go cell by cell and count its neighbors. so the first cell results in its 8 neighbors (plus itself) being counted, and the second cell also. but when counting the second cell's neighbors, you're re-accessing 6 cells that have already been accessed from when the first cell was done. this is a huge inefficiency, but there's currently no way to resolve that with mere code analysis. in order to avoid re-accessing cells, we need mathematical analysis, which can only be done after an arithmetic algorithm of CGoL is developed.
as it currently is, each cell on the board cet accessed NINE TIMES
with a perfect mathematical represntation of CGoL, the current speed of computing the next generation of cells can be made almost an order of magnitude faster from this alone.
but it doesn't stop here!
currently there are hash algorithms in golly that are very fast because they store in memory how certain subdivisions of the board evolve, then the next generation for that subregion doesn't need to be recomputed, it simply needs to be accessed from memory which is faster for large enough patterns, especially when you can skip computing generations and just go to when the pattern repeats.
hashing is fast for REPEATING patterns.

but with a mathematical implementation of CGoL, we will no longer be constrained to "hashing" only repeating patterns,
we'll be able to skip past any situation and simply generate the outcome
(ex: 4x3 is 12, we can skip adding 4 to itself 3 times and simply generate its output)
this will make CGoL infinitely faster to compute than as it is now.

one more: working with lists is fast, but not nearly as fast as working with pure binary integers. but staying in the integer domain, and not need lists to keep track of cell evolution, we'll be able to use hardware-level processing!

Anonymous No. 16288515

>>16287757
this is incredible
now someone with a mathematica account needs dump those equations into it

Anonymous No. 16288518

>>16288305
are these schizos in the room with us now, anon?

Anonymous No. 16288525

Posting in epic thread
I don't think /sci/ can appreciate the level of genius OP has demonstrated here.

Anonymous No. 16288582

>>16287532
in equation 9 and 10 you're using lists?
that's cheating

Anonymous No. 16288654

>>16288582
Only using lists for rendering the output. All of the real computation is done without lists. Desmos does not have a better method to render a grid of cells.

Anonymous No. 16288720

>>16288582
>>16288654
https://www.desmos.com/calculator/f4z3s3bmpd
Are you happy now?

Anonymous No. 16288942

>>16287532
I'm a cs brainlet.
Care to explain how you can model a discret process through the evaluation of a function composed by polynomials?
I don't want the details just a general overview of how to think about it.

For example could you model a TIC-TAC-TOE game through the same technique?
Maybe it would be easy to use as an example.

Anonymous No. 16289032

>>16288942
You could read up on diophantine equations, since they provide a method for universal computation. I didn't do anything related to diophantine equations, I just needed to make a function that only returns one for a specific integer. A polynomial can interpolate through an arbitrary set of points, so I constructed polynomials where all of the integers from 0 to 8 are roots except for one, and since the remaining integer is not a root then it does not give zero, and I can multiply by a constant so that it gives one.

Anonymous No. 16289199

>>16288515
What do you want Mathematica to do? Simplify, or just run them?

Anonymous No. 16289245

>>16288515
Here is the Mathematica code:
p=8
c[b_,i_,j_]:=(Mod[b,2^(1+(i-1)+p*(j-1))]-Mod[b,2^((i-1)+p*(j-1))])*2^(-(i-1)-p*(j-1))
k[b_,i_,j_]:=Sum[Sum[c[b,Mod[i-1+ii,p]+1,Mod[j-1+jj,p]+1],{ii,-1,1}],{jj,-1,1}]-c[b,i,j]
r2[x_]:=(1/1440)(x)(x-1)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)
r3[x_]:=(1/-720)(x)(x-1)(x-2)(x-4)(x-5)(x-6)(x-7)(x-8)
B[b_]:=Sum[Sum[(c[b,i,j]*r2[k[b,i,j]]+r3[k[b,i,j]])*2^((i-1)+p*(j-1)),{j,p}],{i,p}]
ListAnimate[Map[ArrayPlot[Partition[
PadLeft[IntegerDigits[#,2],p^2],p]]&,NestList[B,2+4*2^p+7*2^(2p),32]]]

Image not available

1080x2408

Screenshot_202407....jpg

Anonymous No. 16289664

>>16289199
simplification
do you think it's possible?
>>16289199
i don't have a mathematica account

also, picrel shows the rule on its own working with simple modulus (remainder) arithmetic.

Image not available

1080x2408

Screenshot_202407....jpg

Anonymous No. 16289690

>>16289032
here it is again corrected and clearer

newstate=(1-sum%8//4)*(sum%4//2)*(sum%2+state-sum%2*state)

where "%" is the remainder operator, and "//" is division followed by a floor operation (integer-only division)

Anonymous No. 16289710

>>16289664
Very interesting, I'm not exactly sure how that formula works, but it makes sense that something along those lines would be possible.
The version with the polynomials expands to a large size since the polynomial keeps repeating what is fed into it. The simplify function refuses to operate on inputs that large. This might fix that.

Anonymous No. 16289744

>>16289690
I tried to replicate this in Mathematica, and it worked for cell state 0 but not for cell state 1. Perhaps there is some difference between python OOP and Mathematica that I'm missing since I'm not running the python code.
Map[((1-Quotient[Mod[#,8],4])*Quotient[Mod[#,4],2]*Mod[#,2]+1-Mod[#,2]*1)&,Range[0,8]]

Anonymous No. 16289752

>>16288457
If you want to get your game of life to run fast you have to look up how memory latency and simd works.

Here you can learn a little more about it:
https://www.youtube.com/watch?v=9t_Ux_7K-8M

Anonymous No. 16289753

>>16289752
(It's a playlist)

Anonymous No. 16289775

>>16289744
you forgot to treat the last "a+b-ab" as a single unit
(you forgot paranthesis)
here:
Map[((1-Quotient[Mod[#,8],4])*Quotient[Mod[#,4],2]*(Mod[#,2]+1-Mod[#,2]*1))&,Range[0,8]]

Anonymous No. 16289783

>>16289752
mememory optimazation will only result in marginal speedups (~2x)
my goal is to be able compute the nth generation of a board state directly without having to go through the intervening steps.
until then, reducing redundancy where each cell only has to be called once intstead of 9 times will result in 9x improvement.

Anonymous No. 16289794

>>16289775
Thanks, the code works now. The function expands to 1.1 MB instead of 4.1 MB

Anonymous No. 16289796

>>16289794
Simplify reduces it to 700 kB

Image not available

1080x2408

Screenshot_202407....jpg

Anonymous No. 16289804

>>16289710
it simply reduces the neighborhood sum down to its binary and works from there
when taking the mod 2 of an integer, you get its last bit (a 0 or a 1)
by taking the mod 4 of a number (and regularizing it (quotient) you get its second to last bit
and so on

I listed out the binary representation of the integers 0 through 8 and constructed an arithmetic rule to generate the output I wanted

with CGoL it's easy to do this since there are only 3 outputs of 1, the rest (29 of them) are 0. so it's easy to start eliminating whole swaths of possible inputs.

in picrel, the last binary digit is the current cell state the rest are binary representations of the integers 0 through 15.
the rule is just one product of four factors
working from left to right: the first and second factors eliminate any sum greater than 8 and 4 respectively, the third factor eliminates any sum lesser than 2, the final fourth factor is simply an "or" rule
note: "[5]" is a stand-in for the fifth binary term which in this case is the current cell state, [1] is the first term, if [1] is a 1 then the integer being represented is 8 or greater.

Anonymous No. 16289807

>>16289804
also, what I just gave is a trivial formulation for explanation purposes
I had already simplified it down as seen in the rule I gave earlier.

Image not available

1080x2408

Screenshot_202407....jpg

Anonymous No. 16289811

>>16289804
>>16289807
sorry I had an error where I messed up the "or" rule

Anonymous No. 16289823

>>16289794
>>16289796
thanks for letting me help lol

and that's great and all
but does it
1: run faster at execution
2: show the simplify so that we can check for insights (like, what is the arithmetic shortcut!)

Anonymous No. 16289855

>>16289823
Mathematica is definitely optimized for this type of calculation, but I doubt that it will be faster than the built in cellular automation functions. Mathematica does a few symbolic optimizations and compiles down to C.

Anonymous No. 16290102

>>16289855
is there a way to show these symbolic optimizations?
i feel like there should be
pls show them

Anonymous No. 16290415

>>16290102
It's done on the backend with caching and such, I don't think it's very well documented but you might be able to find a video of them talking about it.