2
$\begingroup$

[Updates: Thanks for @Raphael 's notification, I delete the screenshot of the book and type the $LaTex$ materials]

In Sisper's Intro to the theory of Computation, there is a reduction method via Computation History. He proves theorem 5.10 and 5.13 (3rd edition, page223) by that method. (I append the related part at the end)

Take theorem 5.10 as an example, to construct the LBA B, we need to know the computation history in advance. As far as I understand, there is only one way to get this history -- run turing machine on the input. But if we do this, it has chance to bring us to a loop since we don't know if it's gonna halt or not.

If we do this to get the Decider S in the proof (see the appended proof), we can not say that S is a decider, because in step 1 where we construct the LBA B, we may not halt. So the proof doesn't work.

Thanks for @fade2black 's explanation, let me clarify my question further:

In the proof, we are constructing a decider S for $A_{TM}$. For a decider, we expect tow things:

  1. On input in the language, it halts and accepts
  2. On input not in the language, it halts and rejects

Now let's consider the Decider S in the proof. It works well on $<M, w>$ where M accepts w. It satisfies the first condition above.

But if it is given an input $<M, w>$ where M dose not halt on w, problems can happen. The first behavior of Decider S is to construct B from $<M, w>$. Now since M does not halt on w, we don't have a accepting history. Without an accepting history, how can we construct B? You may argue that if M does not halt on w, just let B accept nothing. But I want to ask: How do you know in advance that M does not halt on w? For me, the only way is to run M on w. If M does not halt, we know that M does not halt on w. But that is to say, we run M on w for the purpose to construct B, which is the first step in Decider S. $\textbf{This Step May Never Halt}$, thus S may never halt. Therefore we know that S is not a decider (A decider must halt no matter it accepts or rejects).

Can any one correct my thought? Thank you.

Here is the related part in the book. (All the following is a paraphrasing of Theorem 5.10 from $\textit{Introduction to the Theory of Computation}$, third edition, Micheal Sisper)


$E_{LBA} = \{<M>|\text{M is an LBA where } L(M) = \emptyset\}$

  • LAB stands for Linear Bounded Automaton. But it seems you don't need to understand LAB to answer my question, since I'm asking about his methodology of using Computation History.

$\textbf{Theorem 5.10}$

$E_{LBA}$ is undecidable.

$\textbf{Proof Idea }$ This proof is by reduction from $A_{TM}$. We show that, if $E_{LBA}$ were decidable, $A_{TM}$ would also be.

  • Note that $A_{TM} = \{<M, w>|\text{M is a Turing Machine and M accepts w}\}$

We will construct a $LBA$ B. The language B recognizes comprises all accepting computation histories for M on w. So if we can determine whether B's language is empty, clearly we can determine whether M accepts w.

Now we construct B from M and w. Assume $x$ is an accepting computation history for M on w. For the purpose of this proof we assume that the accepting computation history is presented as a single string, with the configurations separated from each other by the $\#$ symbol, i.e. $x = \# C_1 \# C_2 \# ... \# C_l \#$.

The LBA B works as follows. When it receives an input $x$, B is supposed to accept if $x$ is an accepting computation for M on w. B can just check whether the $C_i$ satisfy the three conditions of a computation history.

  1. $C_1$ is the start configuration
  2. Each $C_{i+1}$ legally follows from $C_i$
  3. $C_l$ is an accepting configuration for M

If 1, 2 and 3 are satisfied, B accepts its input.

$\textbf{Proof }$ Suppose Turing Machine (TM) R decides $E_{LBA}$. Construct TM S that decides $A_{TM}$ as follows.

S = "On input $<M,w>$, where M is a TM and w is a string

  1. Construct LBA B from M and w as described in the proof idea.

  2. Run R on input .

  3. if R rejects, accept; if R accepts, reject."

Then this S is a decider for $A_{TM}$. This contradicts to the fact that $A_{TM}$ is Turing-undecidable.

$\endgroup$
1
$\begingroup$

It seems you confused two things

  1. What computation history is and
  2. How the hypothetical decider $R$ and LBA $B$ are used to decide $A_{TM}$

You can think of TM configuration as snapshot of the tape content plus machine's state at some particular time. Every step of a TM generates a new configuration. The set of all that configurations is a computation history. If computation halts then that set is finite. So, if $C_1\#C_2\#\dots \#C_n$ is a sequence of configurations and $M$ is a TM, you can check if a configuration $C_i$ is a legal configuration with respect to the TM $M$. We can also check if two adjacent configurations $C_i\#C_{i+1}$ is a legal pair of configurations., i.e., if $C_{i+1}$ legally follows $C_i$ with respect to TM $M$. In other words, we want to be sure that machine's transitions between states were really made according to the machines's transition rules. In addition we can check if some configuration represents a start configuration or accepting configuration of a TM $M$ on some input $w$.

Now, we can construct a LBA $B$ which takes input $x$, in fact, a computation history for $M$ on $w$, and accepts $x$ if it is accepting computation history. In other words, what $B$ does is it takes $x = C_1\#C_2\#\dots \#C_n$ and checks if it is legal sequence and if it is accepting. At this point you may object: What if $M$ on $w$ never halts? The answer is that we construct LBA $B$ which recognizes only those $x$s (histories) that correspond to the accepting ones for $M$ on $w$. In fact we never simulate $B$, we simply feed it to our hypothetical decider. (I would write it LBA $B_{M,w}$ rather than $B$ to avoid confusions). Thus, $M$ halts on $w$ iff the language of LBA $B$ is not empty.

Now, our algorithm as following:

   decide(M,w)
     construct LBA B for <M,w>
     Run the hypothetical decider R on B
     if answer is ACCEPT, i.e. language of B is empty (no accepting history for M,w)
       REJECT and halt
     else
       ACCEPT and halt
     end
   end

Note that we do not bother with running or simulating $B$, we just construct it. In fact, $R$ takes care of it. Since we have just constructed decider for $A_{TM}$, such $R$ cannot exist. Q.E.D

$\endgroup$
  • $\begingroup$ Thanks a lot for your detailed explanation! But I'm not convinced about the construction of B. Let me say it in tow cases: Case 1. For an input <M, w> where M accepts w. To construct the LBA B. we need the accepting history {C_i}. How do we get this accepting history if we don't really run M on w? Case 2. For an input <M, w> where M doesn't halt on w. Then we don't have an accepting history $x$. So it's impossible to construct the LBA B described in the proof, right? $\endgroup$ – Xiao Liang Sep 2 '17 at 15:47
  • $\begingroup$ I understand your point that we don't need to run the LBA B, so we don't worry about the case where it will not halt. But what I'm confused is that: we have to construct the B for all possible input. But for some input (my Case 2 in the above), we can't construct the B, let alone feeding B to S. $\endgroup$ – Xiao Liang Sep 2 '17 at 15:50
  • $\begingroup$ @XiaoLiang we don't need to know the computation history to construct $B$. The computation history is used as input to $B$. When we construct $B$ we construct it according to $M$ and $w$. In fact $B$ does not care if $M$ halts on $w$. $B$ is supposed to take the computation history as input, parse it and checks this computation is legal and if it leads to the accept state. $B$ doesn't even have to simulate, it simply checks all $C_i$s. $\endgroup$ – fade2black Sep 2 '17 at 20:35
  • 1
    $\begingroup$ Oh, yes, you are right! I understand your point now. To build B, we only need to know <M> and w. Since the description of M gives us the state $q_0$ and $q_{accept}$, which we need to check $C_1$ and $C_l$. To check the relation for $C_i$ and $C_{i+1}$, we don't need the True Accepting History either. We just check whether they are identical except for the positions under and adjacent to the head in $C_i$. $\endgroup$ – Xiao Liang Sep 2 '17 at 22:48
  • 1
    $\begingroup$ Previously, I mistakenly thought that B run M on w to get the TRUE Accepting History. And then B uses this history as a criterion to decide whether to accept an input $x$, which could be a True Accepting history of faked accepting history. But with your explanation, I realized that the beauty of this method is that the B don't need to know the True answer (the accepting History of M on w), but it can still judge whether the thing you feed it with is true or false. Thank you very much for your patient explanation! $\endgroup$ – Xiao Liang Sep 2 '17 at 22:54

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.