What does a non-deterministic guess "look like"?

Question

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.

Answer 1

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.