turing machine with exactly 42 states / state that is visited at least 42 times I am trying to solve the following problems:
Proof wether the following problems are decidable/undecidable:


*

*Given turing machine M: Does M have exactly 42 states?

*Given turing machine M: Does M have a state that is visited at least 42 times when started on an empty tape?

*Given turing machine M: Does M have a state that is visited no more than 42 times when started on an empty tape?


I am fairly new to the topic of computability theory and my intuition are the following:


*

*Decidable, since the number of states might somehow be established by the encoding of the turing machine (I have read something about the encoding by a Gödel number online, however, we have not learned this in my lecture yet).

*and 3. are probably undecidable. I tried to prove this by reducing the problem to the halting problem on an empty tape but didn't get the right idea yet.
I would appreciate any ideas pointing me in the right direction...
 A: 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.
A: So if you think it's undecidable, the reduction is from the halting problem to problem 2/3. The key step in this proof stems from the fact that if problems 2/3 are indeed undecidable, then you can take any instance of the halting problem, transfer it into an instance of problem 2/3. Solve it there, which implies a solution to the original halting problem. This is the best way I can phrase it without giving away too much of the proof.
