A confusion about the Reduction via Computation History

Question

[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.