1
$\begingroup$

I have been trying to understand the solution to the following problem:

"Show that if $L_2$ and $L_3$ are Turing recognisable, then so is $L_2L_3 = \{w_1w_2 : w_1 \in L_2,w_2\in L_3\}$:

which essentially says to use non-determinism to guess a partition $w$ (say $w=xy$) and run the Turing machines $L_1$ and $L_2$ on $x$ and $y$ respectively.

I'm trying to get my head around what this non-deterministic guess "looks like", i.e. what we would say if we were to describe this implementation in more detail.

My thought is if the input string is of length $n$, then the second string $y$ could start at any of the $n$ positions, or be empty, so there are $n+1$ possible partitions. Does this mean we ultimately need to split into $2(n + 1)$ parallel/non-deterministic clones? And how do we manage this splitting in terms of transitions? We obviously don't know the length of the input ahead of time, so we can't immediately have $2(n+1)$ transitions from the start state? Would we scan the input string left to right, spawning two additional parallel threads for each character encountered, or something?

I see this "non-deterministically guess" phrase a lot in example solutions, but I feel like I'm missing a bit of intuition as to why this actually works. Any thoughts would be much appreciated.

$\endgroup$
3
$\begingroup$

Nondeterministic guess is a non formal term we use for two (or more) possible transitions from the same configuration. When talking about a non deterministic finite automata, if a state $q$ has two different transitions for the character $a$, and I want to show that it accepts a certain word $w$, then I treat the junction at $q$ where $a$ is read as the location where the "guess" happens. By "guessing correctly" I refer to the transition that will lead to the eventual acceptance of $w$ (whereas I don't care what would have happened if I took the other transition, the "wrong" guess).

One implementation of guessing a partition of $w$ to $w_1w_2$ would be to have two transitions from the initial state for each character read by the machine head. One transition goes to the state $q$, where $q$ refers to $w_1$ as whatever lies to the left of the current position of the head and $w_2$ as the rest. The other transition stays at the initial state and keeps moving right until it meets blank. Although it's important to realize how to implement such a "guess", it is arguably more important to develop the intuition around the power of nondeterminism and understanding the such a nondeterministic partition can be done (without going through the tedious details and elaborating on the transition function).

For your problem non determinism doesn't really make things much easier, as you could simply execute both machines on every possible partition (of which there are $n$ where $n$ is the input's length) in parallel via dovetailing.

$\endgroup$
4
  • $\begingroup$ For input length $n$, OP is correct, there are $n+1$ partition locations. For example, for $n=1$, the two partitions of the length are $1+0$ and $0+1$. $\endgroup$ – Eric Towers Apr 30 at 21:53
  • $\begingroup$ These are the same. $\endgroup$ – Ariel Apr 30 at 23:12
  • 1
    $\begingroup$ Incorrect. In one case the one character string is recognized by $L_2$ and the empty string by $L_3$. In the other, the empty string is recognized by $L_2$ and the one character string is recognized by $L_3$. There is no a priori reason to expect that either $L_2$ or $L_3$ recognizes the empty string, much less that both do. $\endgroup$ – Eric Towers Apr 30 at 23:14
  • 1
    $\begingroup$ Ah I forgot that there are different languages involved, thanks for the correction $\endgroup$ – Ariel Apr 30 at 23:26

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.