10,821 Pages

## Proof that S(n+1) > S(n)

You probably all know this proof.

Here it is:

1. Simulate the machine for S(n). Instead of halting, go to the new state.
2. Halt using the new state.

## Proof that S(n+1) > S(n) + 1

Peng said in chat that he had never seen a proof of this one before. So, after a while I came up with this:

1. Simulate the machine for S(n). Instead of halting, go to the new state and to the right. Leave the symbol that IS NOT to the right.
2. In the new state go to the left and stay in the new state.
3. Now the head reads opposite symbol as before, as we left it like that in step 1. So now we can use this to halt.

## Proof that S(n+1) > S(n) + 2

1. Simulate the machine for S(n). Instead of halting, go to the new state and to the right. Do not change symbol.
2. In the new state go to the left, leave opposite symbol and go to the old halting state.
3. Now the head reads same symbol as before, as we left it like that in step 1. So now we can use this go to the right again.
4. Now there is opposite symbol at this place and we are in the new state, so we halt.

Let R be the symbol to the right, and H is the other symbol. Here is now the ruleset:

oldhaltingstate oldhaltingsymbol * r newstate
newstate        R                H l oldhaltingstate
newstate        H                * r halt


So, yeah, 3 extra steps.

## Proof that S(n+2) > S(n) + 7

Let R1 be the symbol to the first right, and H1 is the other symbol. Let R2 be the symbol to the second right, and H2 is the other symbol. So the tape looks like this:

oldhaltingsymbol R1 R2


Here is now the ruleset:

oldhaltingstate oldhaltingsymbol *  r newstate
newstate        R1               H1 l oldhaltingstate
newstate        H1               R1 r newstate2
newstate2       R2               H2 l newstate
newstate2       H2               *  r halt


## Proof that $$S(n+k) > S(n) + 3\cdot2^k-k-3$$

Let Rk be the symbol to the kth right, and Hk is the other symbol.

oldhaltingsymbol R1 R2 R3 .... Rn


Here is now the ruleset:

oldhaltingstate oldhaltingsymbol *  r newstate
newstate        R1               H1 l oldhaltingstate
newstate        H1               R1 r newstate_2
newstate_i      Ri               Hi l newstate_(i-1) for all 1<i<k
newstate_i      Hi               Ri r newstate_(i+1) for all 1<i<k
newstate_k      Rk               Hk l newstate_(k-1)
newstate_k      Hk               *  r halt


Now we notice that the number of additional steps $$u_n$$ can be defined by the following recurrence relation:

$$u_{n+1}=2u_n+n+1$$.

With a bit of higher math we find the following direct formula of $$u_n$$:

$$u_n=3\cdot2^n-n-2$$.

To make it sharp inequality, we need to subtract one.

## Proof that S(n+1)-S(n) is unbounded

From the above section we know that $$S(n+k)-S(n)$$ is always at least $$3\cdot2^k-k-3$$. This implies that at least one of $$k$$ differences $$S(2)-S(1),S(3)-S(2),...,S(k+1)-S(k)$$ is equal to at least $$\frac{3\cdot2^k-k-3}{k}$$ (otherwise their sum, which is $$S(1+k)-S(1)$$ would be less than $$3\cdot2^k-k-3$$). So for some $$i$$ we have $$S(i+1)-S(i)\geq\frac{3\cdot2^k-k-3}{k}$$. Because the latter is unbounded (which can be easily shown) it follows that $$S(n+1)-S(n)$$ is unbounded.