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?

  • $\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$ – Apass.Jack Jan 31 at 5:23
  • $\begingroup$ @Apass.Jack did my best to prove more information $\endgroup$ – Xyz Jan 31 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 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 at 8:26

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 are all inputs? Let us fix $\Sigma$, the set of input symbols for Turing machines. The set of all inputs is $\Sigma^*$, the Kleene star of $\Sigma$. Let $E$ be a Turing machine that computes a one-one correspondence $cor$ from $\Sigma^*$ to nonnegative numbers.

In order to specify the behavior of a Turing machine $M$ whose language/encoding is in $TOTOAL$, we will just specify its behavior when the input is a nonnegative integer $n$ with the understanding that we are actually specify its behavior on the input that corresponds to $n$ under $E$.

What is the complement of the halting 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 related to the way how $TOTAL$ is specified?

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

The above quotation of a construction is too brief to be understood correctly easily. Here is a more detailed construction that should be easier to understand.

$M' = $ "On input $x$, use $E$ to compute $cor(x)$. Simulate $M$ with input $w$ as long as possible but for no more than $cor(x)$ steps. If the simulation halts, continue to loop forever; otherwise, halt."

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

The too-brief version equates $x$ with $cor(x)=n$, which could be very confusing for beginners although acceptable for users experienced in the theory of computability.

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" is/represents/encodes the input to $M'$. It is a variable independent of $M'$.

  • $\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 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$ – Apass.Jack Jan 31 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 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$ – Apass.Jack Jan 31 at 9:55
  • $\begingroup$ Running $M'$ a certain number of times to see it's behaviour? $\endgroup$ – Xyz Jan 31 at 9:57

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.