0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As there was some misunderstanding, what do you mean by "looping" Turing machine? Does this means that some configuration repeats infinitely many times, or just that machine runs infinitely long (here it could or could not repeat some configuration, it does not matter), or perhaps yet something else? $\endgroup$ – dtldarek Feb 22 '14 at 18:03
  • $\begingroup$ @dtldarek loop means that the machine runs infinitely long (analogous to being stuck in a while loop, for example). I hope this helps! :) $\endgroup$ – user1038665 Feb 22 '14 at 19:47
  • $\begingroup$ What is wrong with using "not halting" for "not halting"? :P As edited into my answer below, I would read "looping" as a technical term for repeating configurations. $\endgroup$ – Arno Feb 22 '14 at 20:28
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Regarding the second question, there can be an infinite loop and still no configuration might be repeated. 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. $\endgroup$ – dtldarek Feb 22 '14 at 17:57
  • $\begingroup$ A Turing machine is defined to loop if it repeats a configuration. It starts to make sense the other way around: A Turing machine can very well neither loop nor halt. $\endgroup$ – Arno Feb 22 '14 at 17:59
  • $\begingroup$ Alright, there is a misunderstanding on the meaning of "loop" in the context of Turing machines. I had removed my downvote and I will ask the OP for clarification. $\endgroup$ – dtldarek Feb 22 '14 at 18:01
  • $\begingroup$ The OP answered, see his comment. $\endgroup$ – dtldarek Feb 22 '14 at 20:14

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.