I'm not following this proof of what Bools,Burgess,Jeffrey call the productivity function. The proof states that the value from the productivity function is not computable. They call it $s$, and it computes a score for a $k$-state Turing machine, $s(k)$. They construct a new machine with one more state ($k + 1$ states), that computes another value $t$. But then they say the machine to compute $t$ only has $k$ states. This is confusing because it was just defined as having one more than $k$ states.
It seems like the machine to compute $t$ should have $k+1$ states (by definition), which isn't a contradiction, and also doesn't prove anything. What am I not understanding?
Consider a $k$-state Turing machine, that is, a machine with $k$ states (not counting the halted state). Start it with input $k$, that is, start it in its initial state on the leftmost of a block of $k$ strokes on an otherwise blank tape. If the machine never halts, or halts in nonstandard position, give it a score of zero. If it halts in standard position with output $n$, that is, on the leftmost of a block of $n$ strokes on an otherwise blank tape, give it a score of $n$. Now define $s(k) =$ the highest score achieved by any $k$-state Turing machine. This function can be shown to be Turing uncomputable.
We first show that if the function $s$ were Turing computable, then so would be the function $t$ given by $t(k) = s(k) + 1$. For supposing we have a machine that computes $s$, we can modify it as follows to get a machine, having one more state than the original machine, that computes $t$. Where the instructions for the original machine would have it halt, the instructions for the new machine will have it go into the new, additional state. In this new state, if the machine is scanning a stroke, it is to move one square to the left, remaining in the new state; while if it is scanning a blank, it is to print a stroke and halt. A little thought shows that a computation of the new machine will go through all the same steps as the old machine, except that, when the old machine would halt on the leftmost of a block of n strokes, the new machine will go through two more steps of computation (moving left and printing a stroke), leaving it halted on the leftmost of a block of $n + 1$ strokes. Thus its output will be one more than the output of the original machine, and if the original machine, for a given argument, computes the value of $s$, the new machine will compute the value of $t$.
Thus, to show that no Turing machine can compute $s$, it will now be enough to show that no Turing machine can compute $t$. And this is not hard to do. For suppose there were a machine computing $t$. It would have some number $k$ of states (not counting the halted state). Started on the leftmost of a block of $k$ strokes on an otherwise blank tape, it would halt on the leftmost of a block of $t(k)$ strokes on an otherwise blank tape. But then $t(k)$ would be the score of this particular $k$-state machine, and that is impossible, since $t(k) > s(k) =$ the highest score achieved by any $k$-state machine.
Thus we have proved:
4.3 Proposition. The scoring function $s$ is not Turing computable
pp 40-41 Computability and Logic, Fifth Edition. Boolos, Bergess, Jeffrey.
Maybe it helps to picture what is going on.
First, let's define $[k]$ to be the tape/head configuration that is used to represent a number $k$, which is a block of $k$ consecutive strokes on an otherwise blank tape, and with the read/write head on the leftmost stroke. Below is a picture of what $[5]$ looks like (I use $1$ for strokes and $0$ for blanks):
With this representation convention, we can define what it means for a Turing-machine to compute some function. In particular, let's say that a Turing-machine computes a function $f(k)$ iff for any $k$, the machine, when started on $[k]$, eventually halts on $[f(k)]$.
OK, so now we'll do the proof by contradiction to prove that the scoring function $s(k)$ is not computable. So let's assume it is computable. This means that we have a Turing-machine $S$ that has the following input/output behavior:
Note that we are not saying that machine $S$ has $k$ states (I think that's a point of confusion you have). It has some number of states, but we're actually not interested in that. All we care about is that $S$ is able to have the behavior that for any k: if it has $[1]$ as input, it outputs $[s(1)]$, if it has $[2]$ as input, it outputs $[s(2)]$, etc. And $S$ computing the $s(k)$ function means that it gives the right output value $s(k)$ for any $k$. And remember what that means. If, for example, $s(2)=3$, then what that means is that out of all Turing-machines that have $2$ states and that start with input $[2]$, there is a machine that outputs $[3]$, but there is no machine that outputs $[n]$ with $n \geq 4$.
Now, if $S$ exists, then we can easily extend its program so that when it was normally about to halt (and note: it will be on the leftmost $1$ at that point), it will now move square to the left, print a $1$, and then halt. This is trivial to do, so if $S$ exists, the following machine exists as well:
So here the 'Add 1' subroutine does the adding of the extra $1$. OK, so this new machine, let's call it $T$, apparently computes the function $t(n)=s(n)+1$. But it is also true that $T$ has some number of states. OK, let's say that $T$ has $n$ states. Now let's consider when we input $[n]$ into $T$. Since $T$ is computing the $t(k)$ function, this means that $T$ will output $[t(n)]$. But wait! $T$ is a machine with $n$ states, but that halts with $t(n)=s(n)+1$ consecutive strokes on the output tape on an otherwise blank tape and with the read/write head on the leftmost stroke! That wasn't supposed to happen, given that $s(n)$ was supposed to be the largest number of such $1$'s in such a configuration left by any machine with $n$ states. So, we have a contradiction! So, the existence of $S$ leads to contradiction: $s(k)$ is not computable.
(note that for this last paragraph I started using $n$ instead of using $k$ like the book did, because I think the book using $k$ for that part of the proof may have lead to some confusion on your part as well. Specifically, $n$ is a specific number: it is the number of states of Turing-machine $T$ .. so that's different from the $k$ that we use as a variable for when we talk about $s(k)$ or $t(k)$).