Programmable computer

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
User avatar
Coban
Posts: 26
Joined: June 26th, 2016, 3:50 pm
Location: NYC

Programmable computer

Post by 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
Nicolas

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Post by 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
Coban
Posts: 26
Joined: June 26th, 2016, 3:50 pm
Location: NYC

Re: Programmable computer

Post by 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
Nicolas

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Programmable computer

Post by 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):

Code: Select all

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:

Code: Select all

    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;

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Programmable computer

Post by 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.

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Programmable computer

Post by gameoflifemaniac » January 27th, 2017, 8:28 am

But can you post the same computer but programmed to display the sequence of prime numbers?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Post by 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
Coban
Posts: 26
Joined: June 26th, 2016, 3:50 pm
Location: NYC

Re: Programmable computer

Post by 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...
Nicolas

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Programmable computer

Post by 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 1328 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 1032 times

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Post by 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 46525 times
Unless there's some weird bug in Simeks' program, it works.
While you're at it, assemble this program:

Code: Select all

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
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Programmable computer

Post by 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.
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
Coban
Posts: 26
Joined: June 26th, 2016, 3:50 pm
Location: NYC

Re: Programmable computer

Post by Coban » January 28th, 2017, 6:03 am

Ok, sorry gameoflifemaniac,
Nicolas

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Programmable computer

Post by gameoflifemaniac » January 28th, 2017, 6:05 am

The printer does not print out primes! The squares don't change!
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
Coban
Posts: 26
Joined: June 26th, 2016, 3:50 pm
Location: NYC

Re: Programmable computer

Post by 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?
Nicolas

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Post by 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
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Programmable computer

Post by gameoflifemaniac » January 28th, 2017, 9:58 am

Sorry, I just wasn't waiting long enough!
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
Kiran
Posts: 285
Joined: March 4th, 2015, 6:48 pm

Re: Programmable computer

Post by Kiran » January 28th, 2017, 11:12 am

It takes a bit over 50 million generations to start printing primes.
Kiran Linsuain

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Programmable computer

Post by 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.

Code: Select all

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.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Programmable computer

Post by 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 1049 times

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Post by 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
Coban
Posts: 26
Joined: June 26th, 2016, 3:50 pm
Location: NYC

Re: Programmable computer

Post by 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...
Nicolas

User avatar
Coban
Posts: 26
Joined: June 26th, 2016, 3:50 pm
Location: NYC

Re: Programmable computer

Post by 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
Nicolas

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Programmable computer

Post by gameoflifemaniac » January 29th, 2017, 8:28 am

And is it possible to make it print primes starting from 2?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: Programmable computer

Post by 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
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Programmable computer

Post by 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.

Post Reply