2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Language nitpick: it is "decidable", not "decisive". And it's "computability theory" in English, not "decision theory". The latter is about choosing which action to take as a human with preferences about outcomes. $\endgroup$ – hmakholm left over Monica Jan 16 '15 at 16:09
  • $\begingroup$ @HenningMakholm Thank you - I corrected my post :) $\endgroup$ – eva Jan 17 '15 at 13:08
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ ...or there has to be a state that has been visited 42 times?! So the problem is just a specific instance of the blank tape problem and therefore undecidable?! $\endgroup$ – eva Jan 17 '15 at 13:40
  • $\begingroup$ @eva: Yes to the first part of your comment, no to the second. The point is that you can decide the property simply by simulating $42n+1$ steps of the machine and keep count of how many times each state is seen. Either the machine stops before $42n+1$, and at that time you'll just look at the counts to find the answer -- or it is still running at step $42n+1$, in which case you know the answer must be "yes" even without looking at the counts. $\endgroup$ – hmakholm left over Monica Jan 17 '15 at 13:48
  • $\begingroup$ Beware in particular that a specific instance of an undecidable problem doesn't itself have to be undecidable. For example, the halting problem is undecidable, but if we restrict it to the specific case of machines that don't have a stopping state, it becomes trivial! $\endgroup$ – hmakholm left over Monica Jan 17 '15 at 13:50
  • $\begingroup$ Of course! That makes sense - thank you... I will try to fully "grasp" the answers for 1 and 2 until I proceed to questions 3 ;) $\endgroup$ – eva Jan 17 '15 at 13:55
  • $\begingroup$ Wow - thanks for the explanation concerning 3. I am not quite sure if I can imagine how the machine P would look but I definitely get the idea. The way you constructed steps 1 - 4, is this how reductions are usually done? It seems like this might work on multiple problems with little modifications like the one in our case of making sure that each of MQ's states is actually visited. $\endgroup$ – eva Jan 17 '15 at 14:25
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.