Turing Tumble CPU


#1

I already showed Turing complete machine with TT parts. It can be seen on the link below.
https://community.turingtumble.com/t/counter-machine-in-3360-lines-tt-vba/705
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)


Proof of Turing Completeness?
#2

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.