Introduction
The following game is quite nice: Alice has, in secret, constructed a polynomial $P \in \mathbb{Z}[x]$. On day $n=1,2,3,...$, she secretly writes down $P(n)$ on a piece of paper. Each day, Bob guesses a number $k \in \mathbb{Z}$. If the number agrees with the number Alice wrote down, Bob wins. Otherwise, the game continues next day.
There is a strategy for Bob to win: The set of polynomials, $\mathbb{Z}[x]$, is countable, so Bob makes a list of them (say, ordering the polynomials by total sum of all coefficients, ignoring signs). On day $n$, he guesses the value of $P_i(n)$, where $P_i$ is the $i$th polynomial in his list. Since all polynomials with integer coefficients are on the list, Bob eventually wins.
Question: Suppose Alice instead uses a (fixed) Turing machine (which takes $n$ as input) to generate the integers. Can Bob still win the game?
I used to think that the same strategy applies; Bob makes a list of all Turing machines, ordered by number of states, and perform the same strategy. However, Bob has an issue here, since it is hard to know which Turing machines halt. If Bob had access to an oracle, so that he can ensure only machines which halts on every input, is put on the list, then he should be able to win. But, if Alice has access to the same oracle, she should be able to do a diagonal construction, which outputs $TM_n(n)+1$, where $TM_n$ is the $n$th Turing machine on Bob's list.
However, perhaps Bob can win anyway, (not by consulting an oracle) by ordering his list of Turing machines in a smarter way, so that machines with longer run time are put later in his list. Also, note that Bob does not need to identify the correct Turing machine; he only needs to match the output of Alice for some day $n$.
