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

You probably all know this proof.

Here it is:

- Simulate the machine for S(n). Instead of halting, go to the new state.
- 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:

- 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.
- In the new state go to the left and stay in the new state.
- 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

- Simulate the machine for S(n). Instead of halting, go to the new state and to the right. Do not change symbol.
- In the new state go to the left, leave opposite symbol and go to the old halting state.
- 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.
- 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.