1
$\begingroup$

I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine that the halting problem receives as input) on w(the word received as input) for n steps.

Can somebody explain to me who is n and why do we need to simulate M for n steps? Why not only once?

For proving that halting on all inputs problem is not in RE, the complement of halting problem is used. Supposed we take M(w) as the turing machine used for halting problem, I get the next simulation:

M'= simulate M(w) for n steps; if M(w) halts, make it loop else, stop.

I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

N stands for the length of the word. I don't understand the simulation for a number of steps. Why is that?

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you add a reference to the textbook you are using in the question? All users are not using the same textbook as you. Or you can copy the full or just the relevant text of that proof in the question. $\endgroup$
    – John L.
    Jan 31, 2019 at 5:23
  • $\begingroup$ @Apass.Jack did my best to prove more information $\endgroup$
    – Xyz
    Jan 31, 2019 at 6:53
  • $\begingroup$ Unless you explain the entire proof, it will be very hard to answer this question. We also don't know what $n$ stands for. $\endgroup$
    – Yuval Filmus
    Jan 31, 2019 at 7:32
  • $\begingroup$ @YuvalFilmus I try my best to prove all the information, but that is all it was written.. $\endgroup$
    – Xyz
    Jan 31, 2019 at 8:26

1 Answer 1

Reset to default
1
$\begingroup$

What is the Halting on all inputs problem? It is the problem about the language $$TOTAL=\{⟨M⟩\mid M \text{ is a TM and }M\text{ halts on all inputs} \}.$$

What is the complement of the Halting problem? It is the problem about the language $$\overline{HALT}= \{⟨M, w⟩\mid M \text{ is a TM and }M\text{ does not halt on input } w\}.$$

Given a word $⟨M, w⟩$ where $M$ is a Turing machine and $w$ is a input word, how can we construct a new Turing machine in a way that is similar to/the same as how a Turing machine is described in $TOTAL$?

$M'$ = simulate $M(w)$ for $n$ steps; if $M(w)$ halts, make it loop else, stop.

The construction above is not clear as the meaning of $n$ is defined. Let us clarify that $n$ is the length of the input string. Here is a clear construction of $M'$, where $|x|$ is the length of $x$.

$M' = $ "On input string $x$, simulate $M$ with input $w$ as long as possible but for no more than $|x|$ steps. If the simulation ever halts, continue to loop forever; otherwise, halt."

Now you should be able to check that $$⟨M, w⟩\in\overline{HALT} \Longleftrightarrow M'\in TOTAL.$$

I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

The "N" in "N STEPS" depends on the input to $M'$. It is a variable independent of $M'$.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Let me see if I understood this correctly. It is like, when simulating M for M', you take just a finite part of the inputs w' and simulate M for them in order to see if M will halt or not and if M halts, then you make it loop so that the statement for TOTOAL(TOTOAL halts on all inputs) would be true? $\endgroup$
    – Xyz
    Jan 31, 2019 at 9:30
  • $\begingroup$ No. Given any input $w'$, $M'$ changes it to a number, $n$ using $E$. Then $M'$ simulates $M$ on input $w$ for $n$ steps. Note that $w'$ has nothing to do with $w$. (Hmm, I should have used $x$ instead of $w'$ to prevent relating $w$ to $w'$.) $\endgroup$
    – John L.
    Jan 31, 2019 at 9:35
  • $\begingroup$ And why is a number of steps needed? I mean, M(w) won't have the same behaviour everytime especially beacuse it's related to the same input w on and on? $\endgroup$
    – Xyz
    Jan 31, 2019 at 9:48
  • $\begingroup$ Please think from the following perspective first. How do you construct a Turing machine $M'$? You need to specify how $M'$ runs given any input $x$. Now how can you specify that? how? how? how? We have infinitely many such $x$. $\endgroup$
    – John L.
    Jan 31, 2019 at 9:55
  • $\begingroup$ Running $M'$ a certain number of times to see it's behaviour? $\endgroup$
    – Xyz
    Jan 31, 2019 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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