Tough Turing machine multiple choice questions

Question

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult.

(True/False) The set of C programs that, given input x, reach some for-loop is decidable.

I said this is false, because we can have a C program with input x that runs forever (say, in a while loop), but we would never know that it just doesn't need more time to reach its for-loop.

Given Turing machine M, produce a Turing machine M' such that M' halts and accepts x if M loops on x and M' loops otherwise.

A. Since we can't know if M will halt, we can't know if M' will halt.

B. Since we can't know if M' will halt, we can't know if M will halt.

C. No computer can produce M' from M.

I chose C because I think this is a variation of/is the halting problem.

Given M that takes no input and either accepts or loops, produce M' that enumerates primes if M accepts and enumerates $\emptyset$ if M loops.

A. We can't decide if the machine will enumerate 5.

B. We can't decide if the machine will enumerate 6.

C. No computer can produce M' from M.

I chose A because in the case that M loops, we will never know if it's just taking a very long time to accept.

Answer 1

I'm assuming that "looping" means just to run indefinitely (as opposed to "there exists a configuration that happens infinitely many times" assumed by @Arno).

1. You are correct, this is false. You could append some for-loop to any program and asking about this loop would be equivalent to asking whether program halts.
2. You are correct, no such program could exist. If there would be an algorithm that produces M′ from M, then the halting problem would be decidable: just run in parallel M and M′, and surely one of them would halt after a finite amount time.
3. This depends on the definition of "enumerate".
   • If "enumerates $\varnothing$' means it has to halt after finite time (because the set to be enumerated is finite), then this is equivalent to the previous point.
   • On the other hand, if $M'$ could "enumerate" the empty set forever, then it could be defined as $$\mathtt{if}\ M()\ \mathtt{then}\ primes()\ \mathtt{else}\ empty\_set()$$ and the answer would be A.

I hope this helps $\ddot\smile$

Answer 2

1) You are right. To prove it formally, first note that you can replace any for-loop in a given program by some other equivalent construction, and then you can replace halting by entering some special for-loop. Now the new program reaches a for-loop if and only if the original program halts.

Edit: For me, the word "looping" for Turing machines has a precise meaning, namely that the machine repeats configurations. The two answers below are based on this reading.

2) Here you are wrong. The construction I gave above is reversible. Essentially, make you program store all its prior configurations, and always check if you've already seen the current configuration before. If so, halt, otherwise, continue.

3) Both halting and looping are observable properties, so if a machine either halts or loops, this is a decidable distinction. Consequently, all three statements are wrong.