If less than half the strings of a given length are ever produced, this means that there must be some strings where neither the string nor its negation can be proved, indicating incompleteness. But if more than half the strings are produced, there must be cases where both a string and its negation can be proved, indicating inconsistency. Rules (f) through (i), however, produce exactly half the strings of any given length, and can be considered complete and consistent.

Earlier in this section we discussed cases in which negation simply reverses the color of each element in a string. And as a generalization of this one can consider cases in which negation can be any operation that preserves lengths of strings. … A dot shows at which step a given string first appears—and indicates the shortest proof of the theorem that string represents.

If the rules for a multiway system always increase string length then it is inevitable that any given string that is ever going to be generated must appear after only a limited number of steps. But if the rules can both increase and decrease string length the story is quite different, as the picture on the facing page illustrates. And often one finds that even a short string can take a rather large number of steps to produce.

possible strings of a given length are eventually generated if one starts from the string representing "true". … And similarly, if less than half the strings are generated, there must be some string for which neither that string nor its negation ever appear, implying that the system is incomplete. The pictures on the next page show the fractions of strings of given lengths that are generated on successive steps in various multiway systems.

. • (a) At step t , the only new string produced is the one containing t black elements. • (b) All strings of length n containing exactly one black cell are produced—after at most 2n - 1 steps. • (c) All strings containing even-length runs of white cells are produced. • (d) The set of strings produced is complicated. The last length 4 string produced is , after 16 steps; the last length 6 one is , after 26 steps. • (e) All strings that begin with a black element are produced. • (f) All strings that end with a white element but contain at least one black element, or consist of all white elements ending with black, are produced. Strings of length n take n steps to produce. • (g) The same strings as in (f) are produced, but now a string of length n with m black elements takes n + m - 1 steps. • (h) All strings appear in which the first run of black elements is of length 1; a string of length n with m black elements appears after n + m - 1 steps. • (i) All strings containing an odd number of black elements are produced; a string of length n with m black cells occurs at step n + m - 1 . • (j) All strings that end with a black element are produced. • (k) Above length 1, the strings produced are exactly those starting with a white element.

With r string pairs and n = StringLength[StringJoin[p]] there are 2 n Binomial[n - 1, 2r - 1] possible constraints (assuming no strings of zero length), each being related to at most 8 r! … In general, one condition for a solution to exist is that integer numbers of pairs can yield strings of the same length, so that given the length differences d = Map[StringLength, p, {2}] . {1, -1} there is a vector v of non-negative integers such that v . d  0 . … Yet starting with pair 1, the upper string is longer by 2 A s, and the pairs are such that the length difference must always remain even—preventing the crossover from occurring.

String overlaps The total numbers of strings with length n and k colors that cannot overlap themselves are given by a[0] = 1; a[n_] := k a[n - 1] - If[EvenQ[n], a[n/2], 0] Up to reversal and interchange of A and B , the first few overlap-free strings with 2 colors are A , AB , AAB , AAAB , AABB . The shortest pairs of strings of 2 elements with no self- or mutual overlaps are {"A", "B"} , {"AABB", "AABAB"} , {"AABB", "ABABB"} ; there are a total of 13 such pairs with strings up to length 5, and 85 with strings up to length 6. … There are a total of 36 such triples with no string having length more than 6.

any proof—regardless of length—exists for a specific result in a mathematical system with particular axioms. … In a multiway system, one can imagine identifying "true" with a string consisting of a single black element. … The other two multiway systems are consistent, so that they never generate both a string and its negation.

In each case a string consisting of a single white element is eventually generated—but this takes respectively 12, 28 and 34 steps to happen. The first multiway system actually generates all strings in the end (not least since it yields the lemmas -> and -> )—and in fact strings of length n > 2 appear after at most 2n+7 steps. … The third multiway system generates a complicated collection of strings; the numbers of lengths up to 8 are 1, 2, 4, 8, 14, 22, 34, 45.

The plots to the right give the successive differences in length between upper and lower strings when each new block is added; that this difference reaches zero reflects the fact that the constraint is satisfied. Cases (m)–(s) show constraints that cannot be satisfied by strings of any finite length. When the constraints involve more than two blocks there seems in general to be no upper limit on how long a string one may need to consider to tell whether the constraints can be satisfied.