Talk:Spiral Rise

Completing the Turing Completeness proof

First, note that a tag system doesn't need a special halting symbol, since instead you can double the value of m and have replace every production rule by one that with 0s in every other position, where 0 is a 'null symbol' whose production rule is the empty string. These 0s will never normally be processed as they won't normally be the mth symbol if m is even. Then, the halting symbol is simply one with an odd-lengthed production rule, so from that point on *only* the 0s get processed by the transformation rule, and hence the system will halt. So, we don't need to emulate special behaviour for a halting symbol.

Now; each symbol is going to be represented by two uses of a at a specific offset, hence two 2s will be put into the number, so d should be 4s+1 instead of 2s+1.

Now; a will have 2 halves; an upper half uu and a lower half ll. It will look like this:

2_____uu__________ll
 

Call the distance in base-d digits between the start of the lower half and the start of the upper half X; it can be made much larger than the lengths of each half. Then the distance from the leading 2 to the upper half is X/2, and m is d^X. Hence, 2 uses of a that are sufficiently close together will cause interference between the upper and lower halves that may create new symbols, but will never interfere with the leading 2. Here's a diagram showing several overlapping uses of a:

                                    2_____uu__________ll  - use 1 of a
                        2_____uu__________ll              - use 2 of a
            2_____uu__________ll                          - use 3 of a
2_____uu__________ll                                      - use 4 of a 

The goal now is to design uu and ll such that the interference between them at an offset that represents a symbol will cause a certain string of symbols to be output. Now, if each symbol is represented by 2 uses of a, then there will also be some consecutive uses of a that don't correspond to a symbol - such as use 2 and 3 in the above diagram. However, such interference will always be after an odd number of 2s, and thus never results in a being used when it is processed, since d = 4s+1. Hence, this interference can be ignored.

Now, to design uu and ll:

uu = bn___...___b3___b2___b1
ll = cn___...___c3___c2___c1

They consist of some number of b- and c-sections, with sufficient padding between them such that the a c-section will never overlap with the wrong b-section at any offset that represents a symbol.

Now, if we choose an integer p, we will choose the offsets for each symbol to be of the form kp+1 where k>=1. We will see later that p=3 works. Using E to represent the digit d-1; then we will define

bi = 00E000E0000 [formally: ci * (k'i*p + 1) - it has Es in positions k'i*p+1 and (ki+k'i)p+2]
ci = 000000E000E [formally: E + E * d^ (ki*p + 1) - it has Es in positions 0 and ki*p+1.]

where ki and k'i are integers depending on i. This diagram shows the case p=3, ki=k'i=1.

Now, the bi and ci will overlap perfectly when the offset is ki*p+1; producing an output of 2 odd digits [potential uses of a] at a distance of k'p+1 (representing another symbol).

Can the Es overlap in other ways? No: The other offsets that would make Es overlap in other ways would be (k'-k)*p and (ki+k'i)*p + 2. However, as long as p >= 3, then these offsets have the wrong values modulo p to come from a real symbol.

Hence; bi and ci implement the behaviour "If the input symbol is k, then output symbol k', otherwise ignore it.

With a sequence of such pairs, we can implement instructions of the form "If the input is symbol k, then output <arbitrary string>" and thus create any tag system. QED.

Let me know if there's any problem with this proof.--Jfb (talk) 17:32, 21 November 2020 (UTC)