Turing Tumble Community

Turing Tumble CPU

I already showed Turing complete machine with TT parts. It can be seen on the link below.
But it is very large and difficult to understand. In addition, the gear bit chain used for it is impossible to realize.

By creating a special instruction set this time, I made the TC machine executable at TT.
I made it in Excel’s VBA, In order to grasp it, a synthetic image of TT was created.

It includes six sets of gear bit chains as shown below.
D … direction of program counter
PC … program counter
Ptr … pointer shows which RAM (but sequential access!)
and which direction selected
RAM A … left side 4 bit RAM
RAM B … right side 4 bit RAM
Z … reserve bit for zero check
There is a ROM area on the left and right of the PC.

For the program, it is necessary to configure ROM and RAM as initial value.
When parts are set in ROM as follows,
If RAM A is odd, β€œF” enters RAM B,
If RAM A is even, RAM B remains β€œ0”

Express this as below for easy viewing. Note that the order of ROM is different from the execution order.

In the initial state, β€œD” points to the right and PC is 0. That is, the first ball executes β€œ<” on the upper right.
And Ptr points to β€œA-”.
This, or β€œ>”, is a conditional branch instruction. Details will be described later, but if the referenced RAM A is 0, we will pass through.
That is, PC indicates β€œ|” directly below. Also, Ptr moves 2 as a side effect, and it points to β€œB-”.
Since TT can not read nondestructively as it is, side effects occur.

The next β€œ|” is NOP. That is, it shifts to β€œ=” below without doing anything.
β€œ=” Is HALT, that is, the program stops there.

Here we consider another case.

If the destination of Ptr is β€œX+” or if RAM A is not 0, β€œ<” in the upper right inverts D and branches to the left
(In other words, it passes β€œX-” only when X = 0). As a side effect, subtract 1 from RAM and Ptr moves next.

The PC points to β€œ-” in the upper left. This instruction decrements Ptr by -1.
Ptr is a variable that specifies RAM and its operation and specifies β€œA -”, β€œA +”, β€œB -”, and β€œB +” in this order.
According to the previous command, Ptr indicates β€œA +”, so it returns to β€œA-” by β€œ-” command.

Then execute the above command in the left column.
Since it can not go further up this time, it returns to the β€œ>” at the bottom.

β€œ>” In the lower left shifts to the adjacent column unless RAM A is 0 as well as β€œ<” in the upper right.
Go from β€œ-” in the lower right to β€œ<” in the upper right and repeat < - > - < - > - … until RAM A becomes 0.

After RAM A goes to 0, going to β€œ<” in the upper right will result in NOP-HALT as I just wrote.
On the other hand, when RAM A reaches 0, when reaching β€œ>” in the lower left, go straight there and go to the upper β€œ*”.
At this time, Ptr becomes β€œB-” due to a side effect.

β€œ" Adds or subtracts RAM according to Ptr. That is, since this time is β€œB-”, RAM B changes from 0 to β€œF”.
For example, if β€œA+”, 1 is added to RAM A. After that, shift Ptr by +1. This is actually the same as the side effect of β€œ>”.
By skillfully combining "
” and β€œ-”, it is possible to arbitrarily change the values of Ptr and RAM.

After β€œ*” execution, it reaches β€œ=” above and stops.

Here, write β€œ>”, β€œ<” in further detail.
The first blue ball passes through most of the blocks and reverses only the last β€œZ”.
Furthermore, by falling to the right side, the next ball becomes red.

The red ball reverses β€œD”, ignores the PC and always performs β€œ*” operation.
Ptr points to β€œX+”. Or, if the RAM is not 0, the next ball is blue.
That is, the PC was reversed.

On the other hand, when the condition of β€œX-” and 0 is caught, the next ball is a red ball.
Since the red ball reverses β€œD”, it means that no branching will occur as a result.
Also, the next ball inevitably becomes blue.

In theory, RAM and ROM can be increased any number.
It does not matter the physical limit of the Gear bit.

The attached Excel file also includes examples of counting and addition.
Thank you for reading.
TT_CPU.xlsm (62.5 KB)


This is amazing! Wow! I’ll plan to spend some time with this to figure out what you did, but how cool! I’ve been meaning to do something like this for a long time. This was like a 28-star difficulty puzzle you just solved here.


Hi @Yama-chan,
Thank you for sharing this design. It is quite impressive what you’ve come up with here! Given that you’ve already implemented what appears to be most of a CPU in TT, I’m wondering what you might think about implementing a specific algorithm? I know it seems outlandish, but I’d really like to know how much space & time it would require to implement h(x) = sha256(sha256(x)) in TT as I posted about here: Implementing a cryptographic hash function with TT?

Curious to get your thoughts on the subject! :slight_smile:

It’s very difficult, but here’s a hand-calculated example:

And it looks like it can be configured using branch instructions.
I think that I need 100 times of this board to perform 1-bit operation. There is no basis, but ten times will not be enough.

If you do that with 32 bits, you need to make it 100 times more.

In total, I think that 10,000 times, that is, about 1 million lines is necessary.

1 Like