[Math] Tough Turing machine multiple choice questions

algorithmscomputer sciencediscrete mathematicsnumber theory

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.

Best Answer

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$

Related Question