Consider a special Turing machine that only needs two places on a tape, in other words , the head switches between two places until the machine halts. I am only interested in the case of two symbols.
The halting problem is decidable for such machines because if a configuration is repeated , the machine will never halt, and this must eventually happen, unless the machine halts or leaves the two places.
Let $f(n)$ be the maximum number such a halting machine can make , if it has $n$ states.
Can we determine $f(n)$ without enumerating all Turing machines ?
If yes, can we also find a machine doing the maximum number of steps efficiently ?
For $2,3,4,5$ , the best machines I found , do $4,9,14,17$ steps respectively. Enumerating all machines will soon be no more feasible.
I used a very simple variant of a generic algorithm (I varied some steps of the best machine, hoping to arrive at a better machine), but there should be a more efficient approach.