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.