Hint for (2): Suppose $M$ has $n$ states. After $42n+1$ steps the machine will either have stopped, or ...
(3) is indeed undecidable. Here's a proof sketch, by reduction from the halting problem:
Suppose $Q$ is some machine and we want to know whether it halts on the empty tape. Then we can, in a systematic way, construct a machine $M_Q$ that does the following:
Write a description of $Q$ to the tape.
Simulate the machine whose description is on the tape until it halts. (This includes techniques from the universal machine that you hopefully know how to construct).
Erase the entire contents of the tape.
Once the tape is erased, move to step 1 (that is, M's initial state).
Now, if $Q$ halts, then $M_Q$ will keep looping, doing everything over and over, so each state will be met infinitely many times, which is larger than $42$. On the other hand if $Q$ doesn't halt, then the states that implement step 3 will be executed zero times, which is less than 42.
So if we have an algorithm that decides problem (3), then applying that to $M_Q$ will tell us whether $Q$ halts. And we can obviously write a program that constructs $M_Q$ given $Q$.
Where this gets tricky is in making sure that all of the states in $M_Q$ will actually be seen during a terminating run of $Q$. It might be that there's some feature of Turing machines that $Q$ doesn't actually use -- perhaps it never writes an 1
to the tape and moves left while transitioning to a state whose number is a multiple of 17. And if our universal machine has a state that is only exercised when the machine being simulated does exactly that, then we're in trouble.
A way out would be, after we have programmed the simulator for step 2 of $M_Q$, to find a fixed machine $P$ such (a) when $P$ is started on an empty tape it will halt on an empty tape too, (b) simulating $P$ does exercise every state of the particular simulator we've written.
Then, to decide whether $Q$ halts, form $M_{P;Q}$ (where $P;Q$ is a machine that first does $P$ and then moves to the first state of $Q$) and ask whether this has a state that is visited at most 42 times.
All in all, this proof feels more involved than it ought to be. Perhaps there's a simpler construction that I'm just overlooking.
As mentioned in the comments, this seems to be a perfectly reasonable description of a non-halting Turing Machine. Do you have a particular reason to think that the description of a non-halting Turing Machine would be complicated?
One reason people tend to think that non-halting Turing Machines would be complicated is due to the halting problem, but that's a fundamental misunderstanding. Figuring out if a particular TM halts is often quite easy: any TM that computes addition, or multiplication, or any other total function clearly halts on every input. The difficulty arises when you try to determine the set of all halting TMs.
Best Answer
Your proposed machine will not halt. If by $0$ you mean a blank cell, given a blank tape it will not write anything and forever shift left. That neither writes $n$ nor terminates. If you allow writing either $0$ or $1$ and you start it with one of those under the head it will just write an infinite sequence of that same digit without halting.
For this purpose it is easy to describe a Turing machine that does this. We will start writing from the right. We start at state $0$, write the rightmost bit of $n$, move the tape left, and go to state $1$. Each state writes the proper bit and moves the tape left. The final state halts instead of moving the tape. This machine does not need to consider what is on the tape. It justifies the claim that we can write $n$ with the claimed number of states, but does not show that there is not a smarter machine that can do it in less states.
Most Turing machines that I have seen actually work in base $1$, not base $2$. They represent $n$ by a series of $n+1$ marks, using a blank as the separator between numbers. That is not how this problem is defined.