Decidable languages kleene star closure - question on a proof

I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the original decider of the language to approve the partition of each branch.

My question is, I can't understand how we can do this non-deterministic split on a word whose length we do not yet know. if the word is very big then there exist more partitions, thus more branches are needed.

So, i don't understand how this "non-deterministic split" can be materialized.

Also, if someone has another proof of this closure via turing machines it will be more than welcome!

It can be hard to grasp why we can just reason about an NTM to prove the Kleene star closure for decidable languages. The important fact is that any nondeterministic TM can be simulated by a deterministic TM. In some cases, it will just take a whole lot of time. When the topic is decidable languages, we are only concerned with whether something can be decided or not, regardless of how much time it will take to figure out. Therefore, an NTM will sometimes be more convenient to reason about, as we can abstract the "try all possible ways to do this", into "guess the right way to do this". However, the abstraction is only valid if we have a finite number of possibilities to try, of course.

So, for the Kleene star closure:

Assume that we have a decidable language $A$. Given that $A$ is decidable, there exists a decider for $A$, let us call it $M_A$. From this $M_A$, we can now construct a decider of $A^\ast$, let us call that decider $M_{A^\ast}$.

This is a description of how $M_{A^\ast}$ works:

On input $w$:

If $w = \varepsilon$ (the empty string), accept

For all possible splits of $w$ into $w_1,w_2,...,w_k$: if $M_A$ accepts all the strings $w_1, w_2, ..., w_k$, then accept

If all splits have been tried without success, reject.

Lets look at an example where $A = \{w \in \{a,b,c\}^\ast \; | \; w \; \text{starts with} \; ab \; \text{or ends with} \; c\}$

For instance, we have that $\{c, ab, ac, bc, cc, aac\} \subset A$, but $\{a, b, aa, ba, bb, ca\} \cap A = \emptyset$.

Now, let us look at how $M_{A^\ast}$ will determine whether or not the string $ccab$ is in $A^\ast$:

First, $M_{A^\ast}$ checks the trivial case. Since $w \neq \varepsilon$, it cannot accept right away. It now has to try all the 8 possible splits of $ccab$ listed here:

$S_1 = \{ccab\}$

$S_2 = \{cca, b\}$

$S_3 = \{cc, ab\}$

$S_4 = \{c, cab\}$

$S_5 = \{cc, a, b\}$

$S_6 = \{c, c, ab\}$

$S_7 = \{c, ca, b\}$

$S_8 = \{c, c, a, b\}$

NOTE: $S_8$ contains three , to allow us to split the string $w$ into each of its letters. Since we can either contain or remove each one of the commas, there are $2^3 = 8$ total splits.

You could argue that split $1$ is not a real split, but since it complies with our definition of a split, $M_A'$ has to check whether $A$ accepts all $w' \in S_1$, which is only $ccab$. $M_A$ rejects $ccab$ because it does not start with $ab$ or end with $c$.
In $S_2$, $cca$ is rejected by $M_A$, and hence $M_A'$ does not have to check $b$ and proceeds to split $S_3$.
In $S_3$, both strings are accepted by $M_A$. $cc$ is accepted because it ends with $c$, and $ab$ is accepted because it starts with $ab$. The machine $M_A'$ now accepts, and hence $ccab \in A^\ast$, simply because $cc \in A$ and $ab \in A$.

StackExchange Computer Science Q#19811, answer score: 8