How to compute an arbitrary Boolean function


#1

tl;dr: TT can compute any Boolean function. Link and explanation below.

As the attempt to prove some extensible infinite version of TT (turing tumble) is Turing-complete continues, I haven’t been convinced of a weaker claim: That TT can be used to compute an arbitrary Boolean function. That is, given an arbitrary function f that takes as input N bits, and outputs 1 bit, is there a way to compute f on the TT board. Arguably, if that can be done, then the function computed by any given circuit, being a Boolean function, can be computed with TT.

While this might seem obvious because we can build NAND gates - the issue of connecting them seemed to me to be a potential problem, so I’ve been thinking of a way just to encode a Boolean function directly, and have come up with a completely inelegant, brute-force way to compute any given function. It will require some explanation, but here is an example for an arbitrary function of 3 bits.

It is missing some pieces - you put the pieces in to specify the function.

Here is the idea. This is basically a decision-tree, which tests each of the three input bits, which are specified by the three rows of gear bits. These tests result in eight distinct paths (one for each of the eight possible input bit-settings). The eight paths are what you get coming out of the bottom row of gear bits. To specify a function, ramps are placed just below the gear bits, in the eight locations. A left-pointing ramp encodes that the function to be computed is 0 given that the bits were set to arrive at that point. A right-pointing one means the value of the function should be 1.

For example, the constant 0 function has eight left-pointing ramps just below the bottom gear bits. The constant 1 function has eight right-pointing ramps. The function that tests if the input is equal to either 3 or 7 has the following sequence of ramps: RRLLLLLL, because if the input (the position of the gear bits, with 1-bit at the top) are set to 3 or 7, the ball will come out of the bottom left gear bit.

The output of the function is represented by which interceptor is reached - the left means 0 (false), the right means 1 (true).

It should be easy to see that once a ball starts going left, it will end up in the left (0) interceptor, and once it starts going right it will end up in the right (1) interceptor.

So, this is a decision-tree that is in effect doing a table-lookup of the values of the function. The disadvantage of course is that the encoding of every function of N bits in this scheme requires O(2^N) pieces.

Since this can be generalized to any number N of bits, and any function of N bits, I think it shows that TT is universal.


Proof of Turing Completeness?
Proof of Turing Completeness?
#2

Follow-up. This can be used to compute a function from N bits to N bits, and also with a feedback loop of "C"s as described by @jcross in the thread on Turing Completeness, we can use the N input bits to reflect the output. See my explanation in the Turing Completeness thread.

Edit: Using the same idea, we can create any finite state automaton which takes two inputs (blue ball, red ball). Each is routed to a different half of a decision tree, which reads the current state from a stack of n bits (n layers of the tree), then writes a new state by going through a stack of n writes to the bits representing the state (using @jcross “C” trick), and then the ball gets intercepted. A new input is given by the user by pressing either the blue or red lever.

Second Edit: Here as an example of how to make a finite state machine is a working 3-state machine, with states 00, 10, and 11 (read off of the top two rows of bits. The state transitions are described using the following notation:

(State, new-state-if-blue-marble-received, new-state-if-red-marble-received)

(00, 00, 11)
(10, 10, 00)
(11, 10, 11)

So, for example, if in state 10, and a red marble is received, the new state is 00.

Third Edit:
Here is a finite state machine that reads in a binary sequence of marbles (red = 1, blue = 0), and ends in state 0 if and only if the binary number was divisible by 3. (The state is indicated by the first two rows of bits.)


How to simulate any computer with finitely many pieces