[Math] Show that of Turing decidable languages is closed under concatenation.

computational complexityturing-machines

The question and its answer is found in the following picture:

enter image description here
enter image description here
enter image description here

But I could not understand:
1- why we scan the input tape from left to right until a blank is encountered?

2- Also I could not understand why exactly one tape symbol receives a mark?

Could anyone explain this for me please?

Thanks!

Best Answer

Let $A$ and $B$ be languages. A string $w$ is in the concatenation of $A$ and $B$ if you can write it as $w= ab$, where $a\in A$ and $b\in B$. This means that you can split $w$ into two halves. The first half is a string from $A$ and the second half is a string from $B$.

If you have two decideable languages $A$ and $B$, you can make a decider for $A$ concatenated with $B$ as follows:

Given a two-tape nondeterministic Turing machine,

  1. Nondeterministically guess where to split the string into two parts $w=ab$.
  2. Run the first machine to make sure the first half is in $A$. If it isn't, reject.
  3. Run the second machine to make sure the second half is in $B$. If it isn't, reject.
  4. If the string really is in the concatenation of $A$ and $B$, then one of these guesses will be correct; that nondeterministic branch will accept, so the computation itself accepts.

Everything else is just bookkeeping:

  • "Read until you encounter a blank space" just means "Read the input until you reach the end of the input".
  • "Mark just one of the symbols." This is a way to mark where you think the division $w=ab$ is.
  • So, altogether these two instructions are: "Read each of the input characters, and nondeterministically decide where to divide the input into two parts by putting a mark where the division should happen."