Proof of Turing Completeness?


I made a Turing machine table.
[Simulation link]

The inputs are 0 and 1, whitch value was read from the tape.
There are 4 sets of gear bit chains inside.

The top S0 and S1 are used to decode the head state of the Turing machine.
I decide like that,
A {S0 = :arrow_upper_left:, S1 = :arrow_upper_left:}
B {S0 = :arrow_upper_left:, S1 = :arrow_upper_right:}
C {S0 = :arrow_upper_right:, S1 = :arrow_upper_left:} .

The other two are connected to an external gear bit chain to rewrite the tape and specify the head movement direction.

Depending on the input and the state of the Turing head, the ball will branch to six ways.
Each sets the gear bits to predetermined.
By this, the ball can set each gear bit chain for any state.

The WRT line is extended to the left for convenience of control.
DIR represents the direction of tape travel. In this time, it is represented by one set because it always moves from side to side.
In general Turing machines, the head may not move, in which case two gear bit chains should be consisted.

The outputs may be indistinguishable, and the balls finally gather in one place.
But there is no space this time, so I did not make it.


In addition, I summarized the entire configuration.
[Simulation link]

Basically, you can connect the counters, tapes, and tables from above.

However, if I take ball to that basic stracture,
Read tape -> refer table -> (next ball) -> tape moves -> rewrite tape -> read tape ,
Since tape moves before rewrite, I can not write to the correct location. so then,
Read tape -> refer table -> (red ball) -> rewrite tape
-> (blue ball) -> tape moves -> tape stay* → read tape ,
We assemble the correct sequence using two balls like this.

CTR wire was introduced for motion control of red ball.
In order to stay tape which shown by*, the red ball makes the WRT line EQ.

If this was actually connected, it should be a one-bit two-value, three-state, four-length Turing machine,
But it is may too large to realize.


I built this Busy Beaver function on simulation.

And I uploaded the video.

I made some mistakes with the above commentary.
In the input to the counter, I should put a blue ball in the middle and a red ball on the left and right.
I also fixed the left conversion part of the counter.

Also, I changed the Busy Beaver function from the above explanation.
The reason I did this is to try the more complicated case, writing “0” other than “1” to the tape.

Thank you.


I like your constructions. Of course, the busy-beaver function is not computable, so no TM can compute its value for all inputs.
Perhaps what you have here is a TM simulation for a finite-tape TM that tries to waste time and then halt?

In any case, I think if we’d like a simulation of a general TM, we need to describe the mechanism used to store a potentially unbounded number of bits (that does not depend on the size of the TM). I still don’t see a natural way to do this that is true to the TuringTumble model, and would love to hear ideas.
Lacking that mechanism, while we know that any finite function (or equivalently, TM state transition function, or, computer with finite storage) can be implemented on TuringTumble, the only turing-completeness argument we have is the cellular-automaton one above in this thread.


I think that if the infinite tape is needed, the above configuration needs an infinite height.
It is inconvenient because it does not reach the bottom in finite time.
However, if the tape is finite (as long as it has a sufficient length), the height is also considered finite and not a problem.
I do not know if this is mathematically correct or if it(sufficient length) completely satisfies Turing Complete.


If the tape is finite, then the machine is not as powerful as a general TM; it is only as powerful as a finite state machine. This would not show Turing-completeness. Addressing the unbounded possible computation is exactly what makes this difficult when considering Turing Tumble, IMO.


In constructing Turing Complete, the above board could only handle a finite amount of memory.
Because it starts from one point on the board.
(In the Turing tumble board, the blue ball and the red ball start point are two points, but are substantially the same)
Therefore, consider preparing an infinite number of ball supply units and levers.

As shown above, it is feasible.
Based on this, I built an infinite number of the following units.

This is an implementation of a Turing machine, and Busy Beaver function is described as a sample.
I explain the behavior in the diagram below.

  1. The ball starts when I push the lever
  2. The ball reads 1 bit of the tape and the ball trajectory branches
  3. Read the head status (2bits) and convert it to the ball trajectory
  4. Determine the next head state from the ball trajectory (tape, head state) and write it to the head state gear chain on the left.
  5. Write to the head state gear chain on the right
  6. Write to the current head state gear chain
  7. Determine the tape recording change and direction with the table and press the target lever.
  8. The next ball is released. There can be 4 patterns in recording and direction
  9. Rewrite the tape
  10. Press the lever for the next ball on the right or left
  11. The next cycle begins

I show the capture when I actually did the above.
Since this sample rewrites 6 bits, the tape is 8 bits in the figure.

Before starting

After half a step

After one step

After 2 steps


This is an example, but by reassembling the table
Any Turing machine can be realized.
At this time, in this configuration, the table needs to be copied indefinitely.

To avoid that, add a gear bit to determine the table.
Convert from gear bits to each table like a tournament.
It’s quite large, but it’s not impossible to build a pattern assuming all table conversion patterns.
This gear bit for selecting a table can also be replicated indefinitely with the same “S” chain that copied the head state.