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

Programmable computer

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Programmable computer

Postby Coban » November 19th, 2016, 10:29 am

Hey,
I made an in-game 8bit programmable computer
the computer, logic gates and programming instructions are here:
https://drive.google.com/open?id=0B-4kR ... lhJUUF3Qnc

a video of the computer computing Fibonacci seqence:
https://www.youtube.com/watch?v=8unMqSp0bFY

it is only composed of
-Buckaroo reflectors
-Period-60 glider guns
-Glider duplicators
Coban
 
Posts: 12
Joined: June 26th, 2016, 3:50 pm
Location: France

Re: Programmable computer

Postby blah » November 20th, 2016, 8:35 am

Impressive! I believe this is the first 8-bit computer in a cellular automaton (And first computer of any specific word size in life).

It's definitely my favourite now. Just to get this right, the memory spaces are as follows (correct me if I'm wrong):
32 items of ROM ("Program").
8 bytes of RAM (registers labeled a-h) ("Memory")
1 byte display ("Printer")

It looks like the items in ROM are 18 bits. What are those bits used for?

RAM address 000 ("h") is used as the program counter (PC). I would assume only the least significant 5 bits are used.
Jumpif makes sense, but why is there a GOTO instruction? Wouldn't it make more sense to use "write h (destination)"?

I'll probably write some programs for it myself if I can get python to work. Also, are there any other programs you've written, other than the fibonacci one?
succ
User avatar
blah
 
Posts: 172
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Postby Coban » November 20th, 2016, 4:16 pm

Yes, you're right about memory spaces

The items in the ROM are 21bits:
4 bits for the instruction
3 bits for the write address
3 bits for one read address
3 bits for another read address
8 bits for data to write to the RAM

Yes, only the 5 least significant bits are used for the program counter
Goto is not essential but if you use write h, be careful because the PC is incremented between each line so "write h n" will jump to the line n+1 and you'll have to do "write h 31" to jump to the line 0
Coban
 
Posts: 12
Joined: June 26th, 2016, 3:50 pm
Location: France

Re: Programmable computer

Postby simeks » November 20th, 2016, 6:48 pm

Coban wrote:I made an in-game 8bit programmable computer

This is very cool, nice work!
Instruction time is about 2M ticks, and I get it to run at about 0.4 instructions/s in Golly.
Here's a program to display the sequence of prime numbers (starting at 5 for simplicity):

write e 2
write a 5
write b 3
move b c
write d 1
not a f
increment f
add f c f
jumpif f
goto 24
sign f f
jumpif f
goto 16
add c b c
increment d
goto 5
not d f
add f b f
sign f f
jumpif f
goto 23
add b e b
goto 3
print a
add a e a
goto 2

Pseudocode:

    int tested = 5;
   
lab_6:
        int divider = 3;
       
lab_5:
            int sum = divider;
            int sum_cnt = 1;
           
lab_4:
                if (sum == tested)
                    goto lab_1;
                if (sum > tested)
                    goto lab_2;
               
                sum += divider;
                sum_cnt++;
                goto lab_4;
           
lab_2:
            if (divider > sum_cnt)
                goto lab_3;
           
            divider += 2;
            goto lab_5;
       
lab_3:
        printf ("A prime number: %d\n", tested);
lab_1:
        tested += 2;
        goto lab_6;
simeks
 
Posts: 323
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Programmable computer

Postby dvgrn » November 21st, 2016, 8:05 pm

Impressive construction! Is it okay if I check it in to Golly's online archives? It certainly fits well in the Very Large Patterns category...!

If there's anything particular that should be included in the pattern comments, please post it here or let me know by PM. Otherwise I guess I can borrow something from the readme file.
dvgrn
Moderator
 
Posts: 3870
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Programmable computer

Postby gameoflifemaniac » January 27th, 2017, 8:28 am

But can you post the same computer but programmed to display the sequence of prime numbers?
User avatar
gameoflifemaniac
 
Posts: 312
Joined: January 22nd, 2017, 11:17 am
Location: 54°00'39.4"N 21°43'50.5"E

Re: Programmable computer

Postby blah » January 27th, 2017, 3:12 pm

gameoflifemaniac wrote:But can you post the same computer but programmed to display the sequence of prime numbers?


I second this. I'm too lazy to get python to work, and I'm sure many others share this sentiment.
succ
User avatar
blah
 
Posts: 172
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Postby Coban » January 27th, 2017, 3:32 pm

Hi
@gameoflifemaniac: you can do it yourself, you just have to copy simeks's code into the assembly.py script then run it with golly
@blah: installing python is not difficult at all, you just have to download an installer and click... I am not with my computer these days so you can do it yourself I think...
Coban
 
Posts: 12
Joined: June 26th, 2016, 3:50 pm
Location: France

Re: Programmable computer

Postby dvgrn » January 27th, 2017, 9:35 pm

Coban wrote:Hi
@gameoflifemaniac: you can do it yourself, you just have to copy simeks's code into the assembly.py script then run it with golly
@blah: installing python is not difficult at all, you just have to download an installer and click... I am not with my computer these days so you can do it yourself I think...

For people running Windows, installing Python is usually just a matter of picking the right installer, 32-bit or 64-bit, to match their version of Golly, and running it. There's not much else to do. Golly usually finds the python27.dll that it needs, without any further configuration.

That said, there are quite a few people who seem to have mysterious problems. 32-bit vs. 64-bit is the source of can't-run-Python problems more often than not -- along with the mistake of trying to install Python 3.x instead of 2.7.x with x != 11 ... But it seems as if there's something else that goes wrong on occasion.

I didn't have any trouble running the script. The resulting pattern is attached. Someone with a faster computer could maybe run it and make sure it performs as advertised...?

programmed_for_printing_primes.mc.gz
GOLComputer programmed with simeks' prime-generating code
(635.6 KiB) Downloaded 55 times

programmed-prime_printer2.mc.gz
simeks' updated program for GOLcomputer -- prints first prime at 40M ticks instead of 50M ticks.
(636.77 KiB) Downloaded 58 times
dvgrn
Moderator
 
Posts: 3870
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Programmable computer

Postby blah » January 28th, 2017, 3:59 am

Thanks! I can confirm it works up to at least the second term, which is seven:
awholeprime.png
awholeprime.png (4.6 KiB) Viewed 3392 times

Unless there's some weird bug in Simeks' program, it works.
While you're at it, assemble this program:
write a 1
add a a b
xor a b a
goto 1

I just wrote it. It should simulate a 1D XOR rule (not rule 90 because that may take a while to simulate given how there's no shifts or rotates in the instruction set). I particularly want this because it would be a 1D CA in a computer in the game of life in a computer in real life.
succ
User avatar
blah
 
Posts: 172
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Postby gameoflifemaniac » January 28th, 2017, 5:08 am

Coban wrote:Hi
@gameoflifemaniac: you can do it yourself, you just have to copy simeks's code into the assembly.py script then run it with golly
@blah: installing python is not difficult at all, you just have to download an installer and click... I am not with my computer these days so you can do it yourself I think...

Remember! I did install Python, but it doesn't work.
User avatar
gameoflifemaniac
 
Posts: 312
Joined: January 22nd, 2017, 11:17 am
Location: 54°00'39.4"N 21°43'50.5"E

Re: Programmable computer

Postby Coban » January 28th, 2017, 6:03 am

Ok, sorry gameoflifemaniac,
Coban
 
Posts: 12
Joined: June 26th, 2016, 3:50 pm
Location: France

Re: Programmable computer

Postby gameoflifemaniac » January 28th, 2017, 6:05 am

The printer does not print out primes! The squares don't change!
User avatar
gameoflifemaniac
 
Posts: 312
Joined: January 22nd, 2017, 11:17 am
Location: 54°00'39.4"N 21°43'50.5"E

Re: Programmable computer

Postby Coban » January 28th, 2017, 6:32 am

Ho... Strange, I don't remember having any issue with simeks's program.
Does it come from the computer ? Perhaps it is just very slow?
Coban
 
Posts: 12
Joined: June 26th, 2016, 3:50 pm
Location: France

Re: Programmable computer

Postby blah » January 28th, 2017, 8:10 am

gameoflifemaniac wrote:The printer does not print out primes! The squares don't change!


Are you sure you're giving it long enough? The program presumably has to cycle a few times before displaying the first prime (it starts at 5, 101 in binary). And you are using the download dvgrn posted, right?
succ
User avatar
blah
 
Posts: 172
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Postby gameoflifemaniac » January 28th, 2017, 9:58 am

Sorry, I just wasn't waiting long enough!
User avatar
gameoflifemaniac
 
Posts: 312
Joined: January 22nd, 2017, 11:17 am
Location: 54°00'39.4"N 21°43'50.5"E

Re: Programmable computer

Postby Kiran » January 28th, 2017, 11:12 am

It takes a bit over 50 million generations to start printing primes.
Kiran Linsuain
User avatar
Kiran
 
Posts: 284
Joined: March 4th, 2015, 6:48 pm

Re: Programmable computer

Postby simeks » January 28th, 2017, 3:51 pm

Because of the recent interest, I wrote an updated version of the prime number program:

EDIT: Sorry, forgot the final change I made, updated below.

write f 224
write g 2
write a 5
write b 3
write c 0
not a e
increment e
add b e d
increment c
add d b d
and d f e
jumpif e
goto 14
goto 8
jumpif d
goto 24
not c e
add b e e
sign e e
jumpif e
goto 23
add b g b
goto 4
print a
add a g a
goto 3

The innermost loop is optimized down from 9 to 5 instructions which improves speed a lot. It also works correctly up to the prime number 223 instead of 127 as the previous version.

To generate all prime numbers below 100, the computer must execute 7866 instructions. The cycle time is 2003880 ticks, so that's a total of 15762520080 generations.

With 64-bit Golly 2.8 with 12 GB of hash memory and a step size of 2^18 (8^6) it can reach about 1.2 instructions/s on my computer, so all prime numbers below 100 can be generated in less than 2 hours.
simeks
 
Posts: 323
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Programmable computer

Postby dvgrn » January 28th, 2017, 4:53 pm

simeks wrote:Because of the recent interest, I wrote an updated version of the prime number program...
With 64-bit Golly 2.8 with 12 GB of hash memory and a step size of 2^18 (8^6) it can reach about 1.2 instructions/s on my computer, so all prime numbers below 100 can be generated in less than 2 hours.

Looks good! I've edited my post above to include the reprogrammed version as well. It displays the initial 5=101 binary, at only 40 million ticks now.

For those who don't like waiting even that long, here's the same programmed computer run up to 87.65M ticks, so the 5 has already been printed. The transition to printing 7=111 binary happens right around 88 million ticks

-- How come the 16 bit flickers on for a moment just before the 88M mark, by the way (starting at 87867000, gone by 87946000)? Looks like there's a leftover signal stream that hasn't quite been cleared yet when the "print" signal goes through -- but it cleans itself up very nicely.

The next prime doesn't get printed until 225M ticks. For what it's worth, on my old laptop with only 1.5GB to spare for Golly, it seems as if the pattern runs a bit more smoothly at a step size of 2^16 than 2^18.
Attachments
programmed-prime_printer2+87.65M.mc.gz
Prime printer version 2, primed to print 111 at T=87865000
(697.14 KiB) Downloaded 54 times
dvgrn
Moderator
 
Posts: 3870
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Programmable computer

Postby blah » January 28th, 2017, 5:22 pm

You still haven't assembled the program I wrote, dvgrn. Spreaking of which, how would you calculate a logical (or arithmetic) right shift? A left shift is easy with addition, but what about a right shift? The computer has no shift or rotate opcodes.

I could imagine using an interative process f(n) to find the smallest number x*2>=n or something like that, but that would be impractically slow. Is there a faster way? Seems like coban forgot about shifts or ran out of opcode space or something.

If we figure that out, we can easily write programs for all the elementary CA.
succ
User avatar
blah
 
Posts: 172
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Postby Coban » January 28th, 2017, 5:28 pm

dvgrn wrote:-- How come the 16 bit flickers on for a moment just before the 88M mark, by the way (starting at 87867000, gone by 87946000)? Looks like there's a leftover signal stream that hasn't quite been cleared yet when the "print" signal goes through -- but it cleans itself up very nicely.


Does it continues to flicker after writing ?
I had some synchronisation problems with the printer when I was building the computer but normally the loops before the input of the printer should fix this kind of issues by synchronising the arriving of the data with the writing instruction signal.
Perhaps the loops aren't big enough, I'll try to fix it later...
Coban
 
Posts: 12
Joined: June 26th, 2016, 3:50 pm
Location: France

Re: Programmable computer

Postby Coban » January 28th, 2017, 5:40 pm

Yes blah... I forgoted shifts...
There is enough space for 3 more instructions
I'll add them later, has I sad before I haven't my personal computer with me these days
Coban
 
Posts: 12
Joined: June 26th, 2016, 3:50 pm
Location: France

Re: Programmable computer

Postby gameoflifemaniac » January 29th, 2017, 8:28 am

And is it possible to make it print primes starting from 2?
User avatar
gameoflifemaniac
 
Posts: 312
Joined: January 22nd, 2017, 11:17 am
Location: 54°00'39.4"N 21°43'50.5"E

Re: Programmable computer

Postby blah » January 29th, 2017, 9:08 am

gameoflifemaniac wrote:And is it possible to make it print primes starting from 2?

That would be essentially trivial; just append some print instructions (assuming you have the space in memory). Maybe the loop could be started earlier, too.
succ
User avatar
blah
 
Posts: 172
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Postby dvgrn » January 29th, 2017, 12:07 pm

blah wrote:You still haven't assembled the program I wrote, dvgrn.

True enough. It's better if I don't get into the business of running Python scripts for everyone who is too lazy to get Python to work (as you put it a couple of days ago).

It'd be much better if I can figure out why people find Python so hard to install, and improve Golly's instructions and/or error messages somehow. It really does take less than five minutes for most people to do the complete installation. Download 32-bit Python 2.7.13 if you downloaded the default 32-bit Golly, otherwise choose the 64-bit Python 2.7.13 installer.

After Python is installed, scripts usually Just Work. If they don't, let me know (by mentioning your OS details and the names of the Golly and Python installers you used). Seems like we need more data points.

Another perfectly good option is for someone to convert the assembly.py Python script into Lua. It shouldn't take that long to do that -- and then it will Just Work in Golly 2.9b1 and later, without any additional installs. But again, just in self-defense, my plan is to encourage other people to get good at Python-to-Lua translations, not do them all myself.
dvgrn
Moderator
 
Posts: 3870
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Next

Return to Patterns

Who is online

Users browsing this forum: Google [Bot], Yahoo [Bot] and 3 guests