Now we are pushing the boundaries of computing down.
Busy Beaver? Refer to https://en.wikipedia.org/wiki/Busy_beaver
To make the experience fit your profile, pick a username and tell us what interests you.
Portable Network Graphics (PNG) - 105.75 kB - 08/02/2020 at 07:30
Busy Beaver 4 code
sheet - 73.75 kB - 08/02/2020 at 07:30
An Arduino script for Nano Flash ROM programmer.
x-arduino - 9.87 kB - 08/02/2020 at 07:30
Adobe Portable Document Format - 33.61 kB - 10/07/2017 at 08:00
I got the new board made, and failed again. Worse this time, it was bi-stable and same fault.
I had a good look and found the design fault. Basically I need to latch the old state and do the operations before setting the new state. I could not see an easy fix. Yes I could code around the fault but it would be messy.
1 Keep the basic reset and clock (why not):
Don't worry about the duty cycle, that is because the Tina 74LS132 is not a schmitt trigger and the patched schmitt trigger is TTL only.
2 Generate a "Clear" signal that is a cleaned up the "Clr" signal.
3 Generate a two PHASE clock (low for setting the symbol and high to move the tape):
4 Decode the new instruction.
Here is the instruction decode mapping. Phase is from the Reset/Clock logic, Write, M0 and M1 are from the Flash ROM, and S1 and S1 are for the shift registers:
This simplifies to:
And here is the decoder, it honours the Write signal when the PHASE signal is low, and the move signals (M0 and M1) when PHASE is high:
Now the above will not make sense to you unless you have had some experience with logic design. I used "Logic Friday" to work all this out (if your interested).
I started writing the Finite State Machine (FSM) code and I realised I did not need the WRITE signal, so my decoder was over designed. Here is the updated version
So the updated decoder truth table is:
And the new schematic:
I need to let the dust settle on the design and the recheck it.
Well it really has been a long time (it is now 13/07/20)! Anyway, The 74HC194 only arrived about two weeks ago, and someone is actually interested in the project.
I thought I had sent off the PCB to be made and had stacked them away, but a full search only found old PCBs. My JLCPCB does not seem to have a record of the PCB (but they delete old PCBs from time to time).
Rereading my log, I am supposed to check schematic. I am not going to see though a faulty design assumption. That has to wait until I build it and I find it does not work. The main error I make at this point is hooking the schematic up wrong, so I will check that.
Well, I did not follow the clock schematic above?!
Okay, checked if the logic works, no, so it is a mistake. I could not find the Tina model for the schematic for the clock reset, so redesigned it. Seems to work:
I have the new board and the components so tonight I will assemble.
I am pretty sure the Flash ROM is still current.
Assembled and powered up. Does not work as expected. Coding error? I have checked this so many times. There seems to be an extra move as every second LED lights up.
Oh well, back to looking at the schematic. No can't see anytning.
False Fail - Success
Okay, I checked the code on the Flash chip and it was old. So I flashed the new code and it works:
The only issue is that the "progression" is a mirror image. Easy fix, it is just an edit of the spreadsheet code and another (final) upload to the flash:
So FINALLY finished! ;)
Here is a video presenting the project:...Read more »
My last build was not 100% successful. Yes the machine was doing something but not as intended. I sort of worked out that it was not executing the first instruction (address 0) but I did not fully investigate this premise.
Anyway I checked the schematic today and it seems to be the case. It cannot execute address 0 after a reset. So I have modified the schematic to fix:
I have updated the design. So a PCB is ready for manufacture. I will wait until I have another PCB ready for manufacture before sending off. It helps reduce the postage cost.
I was not very happy with the last design as it was a bit of a "patch", so I redesigned from scratch. Here is the signals schematic:
As you can see, a write or mark signal is now automatic (no need to be programmed). The following move commands (S0 and S1) are no move, left, right or no move with write.
Here is the new full schematic:
It still needs to be checked and I have run out of 74HC194 chips so I will have to order some more (while the PCB is being made).
I assembled the new board just before going on holidays.
First test showed some activity but not the Busy Beaver:
Okay, I will sort this out when I come back from holidays.
I checked the code and find an error.
Fixed the error still not working.
Realise I have a problem because I don't latch "Din" to the Flash ROM.
As soon as the mark state changes the next state will be wrong (I need to latch Din).
The A0-4 oscillates between 00000 and 00011 which results in Mark 1 and move Left (which is observed). This is state A and state B.
ADR0-4 cycle between 00000, 00010, 00001, 01001. Only the first and third next states are latched.
It appears to be working otherwise.
So if I latch Din with ADR0-4 it should work!
Updated the schematic to latch Din at the beginning of each instruction pair:
I will double check it tomorrow before sending it off for manufacture.
I cut out the 74HC132 but damaged the board getting the solder out of the plate through holes. Decided to get another PCB made and fix some other problems as well:
So now I have to wait.
Have PCB and the main components, forgot to order the 74HC194s.
So a couple of days to wait. I suppose I should look at the code for the FSM in the mean time. Here are the Busy Beaver FSMs:
For my machine, the BB IV will require four state pairs. The first sub-state will read/write the LED, the second sub-state will shift (left, hold or right) the LEDs. The tape is 16 LEDs that should be enough the contain the output.
Actually looking at the output there is an unlined "1" that may be the first state, if so then will not fit as the first state is not offset enough! I can patch the board but not a good start. Yes, it will run, it will just push 5 of the bits off the right edge of the tape. As only I will know, no problems!
The assembly is done, just need to code the Flash ROM:
The clock has been slowed down to about 1 Hz.
I coded four state Busy Beaver, flashed the ROM:
Tested the board and fail?
Check the clock, no clock? Checked the schematic and the pin numbers look wrong? They are wrong! This has happened a few times now. It is quite annoying that chips are uploaded with errors:
If you check the datasheet the pin numbers are wrong above.
I can cut the chip out and make up a jump board to try and get it going.
I have been looking at relay shift registers (yes a relay version of the Turing), and Mike Szczys was interested in Modulo 60 counters. Neat, a relay clock perhaps. Anyway here is a Modulo 60 design using D-type flip flops:
The start up is not perfect but pretty good.
Next how to decode? Easy, Q and ~Q of each stage can be used to decode "0", "1" etc:
I have knocked up a FSM version of the Turing machine:
It does not look much but here is the EasyEDA version that includes the Flash ROM:
Yes that is only seven chips. I have also discovered the 72HC273.
I have been looking at FSM design and found these lecture notes (some students have all the fun!):
They step through the design of a FSM as shown above. The reason I was looking was that 1.5M transistor ROM is cheating for a Turing Machine. As the lecturer says, you can always replace the ROM with combinational logic.
The other reason I was looking is that this machine would be a good target for a Relay Computer. I found a D-Type Flip Flop (that does not use diodes) (source: http://relaysbc.sourceforge.net/circuits.html). Here I have set the D-Type Flip Flop as a counter:
The relay model has been set up to match the Takamisawa A-5W-K relays I have.
Here is a timing diagram and the instruction set:
Looking at Busy Beaver IV:
The coding is reversed (easy fix) but the code executes a shift and a write at the same time. My code has these instructions separated. I can code Busy Beaver but I will require twice as many instructions (i.e. cards or states).
If I want to execute this code directly, I will need a four phase clock rather than the current two phase clock, and some decoding logic.
On a new instruction, the tape has to:
This requires two clock cycles.
Finally in the Busy Beaver IV code, the Halt has been present as a state rather than an instruction. This technically does not work as there is no halt instruction per say. I will need to keep the my Hold instruction to be used with a Halt state. So Busy Beaver IV will need 5 cards.
Reset is a bit tricky for a FSM. Really it is a restart. The process is to tri-state the FSM output so that the pull down (or up) resistors can impose a restart address and instruction.
This is repeatedly executed until the reset signal is lifted. The reset signal has to be synchronised with the clock so that clock is in the correct phase upon start up for the first instruction.
So back to the drawing board, increase the FSM capacity and consider a four phase clock, tape decoder and restart logic.
Here is my preliminary schematic for a Turing machine. It has four cards (four instructions), and a 16 bit "tape" or display. It should be able to play Busy Beaver III (https://en.wikipedia.org/wiki/Busy_beaver). I may extend the tape so it can play Busy Beaver IV:
The top half of the schematic is a Finite State Machine (FSM) and the bottom half is the LED ribbon.
Here are the Busy Beaver programs (III, IV and V):
Here is a Busy Beaver "tower":
Become a member to follow this project and never miss any updates