turing machine with exactly 42 states / state that is visited at least 42 times

Question

I am trying to solve the following problems:

Proof wether the following problems are decidable/undecidable:

1. Given turing machine M: Does M have exactly 42 states?
2. Given turing machine M: Does M have a state that is visited at least 42 times when started on an empty tape?
3. 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:

1. 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).

2. 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...

Answer 1

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:

1. Write a description of $Q$ to the tape.

2. 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).

3. Erase the entire contents of the tape.

4. 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.

Answer 2

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.